【wikioi】1014 装箱问题
2024-08-29 12:27:20
算法:动态规划(01背包)
01背包思想:依次对待某一物体,考虑是否放入容量为V的背包中
用f[V]来表示容量为V的背包的最大价值,则决策是
f[V] = max{f[V], f[V-v[i]]+w[i]} (0 <= i <= n, V-v[i] >= 0)
解释:每一个物体i,只有两种选择,是否放入(放入后一定体积要等于容量V)容量为V的背包中,如果放入的话,那么就要比较现在容量为V的背包不放入i物体 与放入i物体到容量为V-v[i]的背包(价值即为f[V-v[i]]+w[i])哪个大,比f[V]大的话,那么就放入此物体i到容量为V的背包中
(自己慢慢体会,看白书有讲)
注意:此题只需将w看成是物品i的价值,算出最大价值再用v减去就是答案
设状态f[v]表示v容量的背包的最大价值,则
f[v] = max{f[v], f[v-w[i]]+w[i]} (0 <= i <= n) 其中w[i]表示物体i的体积(价值)
优化空间采用滚动数组,从后向前递推
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 35, V = 20005;
int f[V], w, v, j;
int main()
{
cin >> v >> w; //不需要读入n,,对于下面那句来说没有必要
//滚动数组 w既表示体积,又表示价值
while(cin >> w)
for(j = v; j >= w; j--) //依次判断是否将物体放入容量为j的背包中
f[j] = max(f[j], f[j-w]+w);
cout << v - f[v];
return 0;
}
最新文章
- (转载)JAVA线程池管理
- WhaleSong
- 自适应学习率调整:AdaDelta
- WIFI 物理组件
- SSH整合_struts.xml 模板
- 用sinopia搭建npm私服
- SQL Constraint/Index
- structs2的核心和工作原理
- Android 环境搭建、基础窗口window/Mac
- https://doc.opensuse.org/projects/kiwi/doc/
- Go-延时函数defer
- spak数据倾斜解决方案
- MVC 深入讲解Routing _路由规则【八】
- PowerBI开发 第十五篇:DAX 表达式(时间+过滤+关系)
- LeetCode168.Excel表列名称
- [UE4]运行模式
- Android SDK Download List
- [lr] 基本色调调整和色调曲线
- 开发中常遇到的Python陷阱和注意点-乾颐堂
- 利用python 学习数据分析 (学习一)
热门文章
- 无废话Android之activity的生命周期、activity的启动模式、activity横竖屏切换的生命周期、开启新的activity获取他的返回值、利用广播实现ip拨号、短信接收广播、短信监听器(6)
- 【131031】asp.net <;%%>;&;<;%#%>;&;<;%=%>;&;<;%@%>;&;<;%$%>;用法区别
- oracle JOB学习(一)---基础
- 咱就入个门之NHibernate映射文件配置(二)
- jquery中append()、prepend()、after()、before()的区别详解
- 简单解释Windows如何使用FS段寄存器
- tnsnames.ora 监听配置文件详解
- KMP算法代码
- SpringRMI解析3-RmiServiceExporter逻辑细节
- Swift3.0语言教程使用指针创建和初始化字符串