题目
有 N 件物品和一个容量为 V 的背包. 第 i 件物品的费用是 c[i], 价值是 w[i]. 求解将哪些物品装入背包可使价值总和最大.
基本思路
用子问题定义状态: 即 f[i][v]表示前 i 件物品恰放入一个容量为 v 的背包可以获得的最大价值. 则其状态转移方程便是:
1 f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
"将前 i 件物品放入容量为 v 的背包中" 这个子问题, 若只考虑第 i 件物品的策略 (放或不放), 那么就可以转化为一个只牵扯前 i-1 件物品的问题. 如果不放第 i 件物品, 那么问题就转化为 "前 i-1 件物品放入容量为 v 的背包中", 价值为 f[i-1][v]; 如果放第 i 件物品, 那么问题就转化为 "前 i-1 件物品放入剩下的容量为 v-c[i] 的背包中", 此时能获得的最大价值就是 f[i-1][v-c[i]]再加上通过放入第 i 件物品获得的价值 w[i].
优化空间复杂度
一维数组的优化:
- mset(f, 0xcf);
- f[0] = 0;
- for (int i = 1; i <= m;i++)
- {
- for (int j = n; j>= w[i];j--)
- f[j] = max(f[j], f[j - w[i]] + w[i] * v[i]);
- }
- int ans = 0;
- for (int j = 0; j <= n;j++)
- {
- ans = max(ans, f[j]);
- }
- cout <<ans << endl;
初始化的细节问题
我们看到的求最优解的背包问题题目中, 事实上有两种不太相同的问法. 有的题目要求 "恰好装满背包" 时的最优解, 有的题目则并没有要求必须把背包装满. 一种区别这两种问法的实现方法是在初始化的时候有所不同.
如果是第一种问法, 要求恰好装满背包, 那么在初始化时除了 f[0]为 0 其它 f[1..V]均设为 -∞, 这样就可以保证最终得到的 f[N]是一种恰好装满背包的最优解.
如果并没有要求必须把背包装满, 而是只希望价格尽量大, 初始化时应该将 f[0..V]全部设为 0.
为什么呢? 可以这样理解: 初始化的 f 数组事实上就是在没有任何物品可以放入背包时的合法状态. 如果要求背包恰好装满, 那么此时只有容量为 0 的背包可能被价值为 0 的 nothing"恰好装满", 其它容量的背包均没有合法的解, 属于未定义的状态, 它们的值就都应该是 -∞了. 如果背包并非必须被装满, 那么任何容量的背包都有一个合法解 "什么都不装", 这个解的价值为 0, 所以初始时状态的值也就全部为 0 了.
这个小技巧完全可以推广到其它类型的背包问题.
一个常数优化
- for(int i=1;i<=n;i++)
- {
- sumw+=w[i];
- bound=max(m-sumw,w[i]);
- for(int c=m;c>=bound;c--)
- {
- if(c>=w[i])
- f[c]=max(f[c],f[c-w[i]]+v[i]);
- }
- }
这对于 m 比较大时是有用的.
来源: http://www.bubuko.com/infodetail-3113751.html