背包问题总结.ppt

背包问题总结 2006年10月 作业题 设有n件物品 重量分别为w1 w2 w3 wn和一个能装载总重量为T的背包 能否从n件物品中选择若干件恰好使它们的重量之和等于T 只需判断有解 搜索法 将解空间表示成树同学们举了很多穷举 递归 回朔的算法 本质上都是用不同的方式遍历这个解空间树 解空间 设Xi表示第i件物品的取舍 1代表取 0代表舍 搜索的空间为n元一维数组 X1 X2 X3 Xn 取值范围为 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 1 1 1 1 解空间图示 以3个物品为例 解 0 1 0 表示 不取物品0 取物品1 不取物品2 root 0 1 0 1 0 1 0 1 0 求解背包问题就变成搜索这棵数 下面列举 只列出常见的方法 方法1 算法描述 访问结点访问左子树访问右子树 实现 booltest v t v为当前物品编号 t为背包剩余容量 测试当前节点if t 0 returntrue if t n returnfalse if t 0 if test v 1 t 访问左子树 方法2 方法2是同学们使用较多的一种方法 思路 按编号从小到大取物品 解空间被分解为n个子集s 1 s 2 s i s i 表示按从小到大顺序取物品 所取第一个物品编号为i的取法 s i 0 则表示有解 实现 booltest I t i为当前物品编号 t为背包剩余容量 if t 0 returntrue for j i j N j if test j t weight j returntrue returnfalse 3 遍历这个树 2 遍历这个树 1 遍历这个树 它遍历这棵树的方法如下所示 root 0 1 0 1 0 1 0 1 上面列举的都是递归的算法 其他还有一些非递归的算法本质上都是遍历这棵树不再列举 动态规划法 递推方程 设F n t 表示用前n种物品装容量为t的背包的方法数则F n t F n 1 t F n 1 t w n F n 0 1 F 0 t 0 F n x 0当x0表示有解当物品重量 背包容量为整数时 子问题重复程度较高 可减少算法的复杂度 当重量和背包容量为小数时 效率会受影响 并不是有的同学说的不能用动态规划求解 这时可用一个STL的map来记录状态算法效率与子问题的重复程度有关具体实现时 可以选择递归算法和非递归算法递归算法重复的子问题会重复计算 动态规划法 实例w 5 3 1 2 7 T 8F n t F n 1 t F n 1 t w n F 5 8 F 4 8 F 4 1 F 4 1 F 3 1 F 3 1 1F 3 1 F 2 1 F 2 0 1F 2 1 F 1 1 F 1 2 0F 1 1 0F 1 2 0F 2 0 1F 3 1 0F 4 8 F 3 8 F 3 6 F 3 8 F 2 8 F 2 7 F 2 8 F 1 8 F 1 5 1F 3 6 F 2 6 F 2 5 算法实现 递归算法 F n t 用前n种物品 填充容量t的方法数if t 0 return1 若t是小数 则改为abs t 0 0 0001if t 0 return0ifn 0return0returnF n 1 t F n 1 t W n 算法实现 非递归算法F T mapm m 0 1 背包容量为0for i 0 ifirstm t W i 1ift W i Treturntrue 贪心法 有些同学尝试用贪心法解决此题 却没有说明贪心法有可能得不到最优解 需要注意 本题并不满足贪心性质 下面的小数背包问题可以用贪心法来解决 扩展 加入物品价值的概念物品可分割物品不可分割物品可多选 扩展1 加上物品价值 从n个物品中选取若干物品装载容量为M的背包 已知 第i个物品的重量是wi 价值是pi i 1 2 n 且每个物品是无法分割的 求 最后装载方案 即总重量小于M 总价值最大 错误方法 贪心法 思路 将物品按照价值 重量的比值排序 优先选择比值大的物品 举例 物品 价值 重量 3 1 2 1 2 1 限重 4如果采用贪心法 只能取第一个元素得到的价值为3 实际上应该取第2和第3个元素得到的价值为4原因是 物品不可分割 导致背包不能装满 降低了前面选择的效用 扩展1 加上物品价值 思路1 搜索法举例 V 12 11 9 8 W 8 6 4 3 T 13解向量 解空间树 root 1 0 1 0 1 0 1 0 对应于可行解x1 1 x2 0 x3 1 x4 0 重量 13 价值28 搜索法 算法就是搜索整个解空间树 比较所有可行解得到最优解 思路2 动态规划法后面的扩展3再谈 扩展2 物品可以任意分割 设有n件物品 重量分别为w1 w2 w3 wn 价值分别为v1 v2 v3 vn 和一个能装载总重量为T的背包 能否从n件物品中选择若干件装在背包中 使背包中物品的总价值最大 物品可以被任意分割 扩展2 物品可以任意分割 思路 贪心法按价值重量比对物品排序 优先选择比值大的物品 对于第i个物品 若w i 小于所剩能容纳的重量 取全部的i物品 若w i 大于所剩能容纳的重量 取所剩能容纳的重量T 的i物品 此时整个选择结束 扩展3 物品可多选 思路 动态规划法设F k y 表示只用前k种物品 背包总重不超过y时背包的最大价值递归方程与边界条件F k y max F k 1 y F y w k v k F 0 y 0F k 0 0F 1 y y w 1 V 1 总结 这次作业总体情况良好 很多同学应用多种算法解决了教材上的背包问题 另外 还收集了一些其他种类的背包问题 思路灵活 思维发散 态度认真 几个注意点 文档描述更清楚点 不要只贴代码 要配合算法 讲解自己的思路 说明自己应用的算法类型 方便助教批改作业 代码中的注释适当多一点 变量命名要和题意结合 要有意义 变量的作用要说明 不要一堆I j k m n 而不说明作用 上传的文件里不要包含可执行程序 压缩包太大 程序要有Makefile文