浅谈几类背包题
浙江省温州中学徐持衡指导老师：舒春平
2008年12月
目录
摘要 (3)
关键字 (3)
正文 (4)
一、引言 (4)
二、背包的基本变换 (5)
①完全背包 (5)
②多次背包 (5)
③单调队列优化☆ (6)
三、其他几类背包问题 (8)
①树形依赖背包（获取学分）☆ (8)
②PKU3093☆ (11)
四、总结 (12)
附录 (13)
参考文献 (13)
文中原题 (13)
摘要
背包问题作为一个经典问题在动态规划中是很基础的一个部分，然而以0-1背包问题为原题，衍生转变出的各类题目，可以说是千变万化，当然解法也各有不同，如此就有了继续探究的价值。
本文就4道背包变化的题做一些探讨研究，提出本人的一些做法，希望能起到抛砖引玉的作用。
关键字
动态规划背包优化
正文
一、引言
背包问题是运筹学中的一个经典的优化难题，是一个NP-完全问题，但其有着广泛的实际应用背景，是从生活中一个常见的问题出发展开的：一个背包，和很多件物品，要在背包中放一些物品，以达到一定的目标。
在信息学中，把所有的数据都量化处理后，得到这样的一个问题：
0-1 背包问题：给定n 件物品和一个背包。物品i的价值是W i，其体积为V i，背包的容量为C。可以任意选择装入背包中的物品，求装入背包中物品的最大总价值。
数据结构与算法论文在选择装入背包的物品时，对每件物品i ，要么装入背包，要么不装入背包。不能将物品i 多次装入背包，也不能只装入部分物品i （分割物品i）。因此，该问题称为0-1 背包问题。
用于求解0-1背包问题的方法主要有回溯算法、贪婪算法、遗传算法、禁忌搜索算法、模拟退火算法等。
在高中阶段，我们所谓的经典0-1背包问题，保证了所有量化后的数据均为正整数，即是一个特殊的整数规划问题，本文中如无特殊说明均以此为前提。其经典的O(n*C)动规解法是：
状态是在前i件物品中，选取若干件物品其体积总和不大于j，所能获得的最大价值为F i[j]，当前的决策是第i件物品放或者不放，最终得到转移方程：
F i[j] = F i-1[j] (V i>j>=0)
F i[j] = max{ F i-1[j] , F i-1[j-V i]+W i } (C>=j>=V i)
其中由于F i只与F i-1有关，可以用滚动数组来节省程序的空间复杂度。以下就是经典算法的伪代码。
1.FOR i: = 1 TO n
2. FOR j: = C DOWNTO V i
3.  Max ( F[ j ] , F[ j-V i ]  +  W i ) → F[ j ]
4. END FOR
5.END FOR
二、背包的基本变换
①完全背包
完全背包问题：给定n 种物品和一个背包。第i种物品的价值是W i，其体积为V i，背包的容量为C，同一种物品的数量无限多。可以任意选择装入背包中的物品，求装入背包中物品的最大总价值。
这个问题完全可以转化为0-1背包问题来解决，即把第i种物品分割成
(C div V i)件物品，再用0-1背包问题的经典动规实现。
但是，这个算法的时间复杂度太高，并不能作为一种实用的方法来实现。
很容易注意到，这个问题对于0-1背包来说，是另一个极端，每种物品都可以无限制地取，只要改变转移方程，就可以构造出新的算法：状态是在前i种物品中，选取若干件物品其体积总和不大于j，所能获得的最大价值为F i[j]，当前的决策是第i件物品放（多件）或者不放，转移方程是
F i[j] = F i-1[j] (V i>j>=0)
F i[j] = max{ F i-1[j] , F i[j-V i]+W i } (C>=j>=V i) //注意第二个是F i而不是
F i-1，与0-1背包区别仅在于此，因为允许在放过的基础上再增加一件。
这样，这个问题就有了与0-1背包一样时间复杂度O(n*C)的解决方法，同样的可以用滚动数组来实现。
1.FOR i: = 1 TO n
2. FOR j: = V i TO C
3.  Max ( F[ j ] , F[ j-V i ]  +  W i ) → F[ j ]
4. END FOR
5.END FOR
②多次背包
多次背包问题：给定n 种物品和一个背包。第i种物品的价值是W i，其体积为V i，数量是K i件，背包的容量为C。可以任意选择装入背包中的物品，求装入背包中物品的最大总价值。
和完全背包一样，可以直接套用0-1背包问题的经典动规实现，但是效率太低了，需要寻更高效的算法。
首先对于第i种物品，不能确定放多少件才是最优的，因为并没有什么可以证明放一件或者全放一定会更优。换句话说，最优解所需要的件数，可能是0到K i中的任何数。
在日常生活中，如果需要能拿得出1到K i的任意整数数额的钱，往往

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。