《简单背包问题专题》由会员分享，可在线阅读，更多相关《简单背包问题专题（2页珍藏版）》请在金锄头文库上搜索。
1、简单背包问题专题作者：炉灰 本文内容遵从 CC 版权协议一：01 背包问题例例题题： ：纪纪老老师师的减肥的减肥计计划划话说，一日我们亲爱敬爱可爱的纪老师为了让自己的体型更加完美，于是乎毅然决然 的加入了减肥大军的行列中来。他打算在 n 小时内将自己的体重从 w 减到尽可能低。纪老 师的减肥方法是不吃饭，而每个小时不吃饭所能减的体重并不相同。同样老师因为不吃而 下降的 hp 也不相同。现在纪老师想让你帮忙求出他的体重最低可以达到多少。 （我想大家 都不希望老师饿死吧_） 输入格式：第一行有三个数，分别是 n、w、HP。第二行到第 n+1 行每行有两个数，分别 表示该小时不吃饭所减的体重 wi
2、和下降的 hpi。每个数间用空格隔开。 输出格式：输出一个数，即老师可以达到的最低体重。 样例输入： 4 200 100 14 90 22 10 90 110 3 99 样例输出： 164 解析：此为典型的 01 背包问题，hp 是背包容量，下降体重 wi 是价值，而每个小时吃不吃 饭则是该物品取不取。该类问题用子问题定义状态：即 fiv表示前 i 件物品恰放入一个容 量为 v 的背包可以获得的最大价值。则其状态转移方程便是：fij=maxfi-1j,fi-1j- hpi+wi。 用递推的 for 结构实现出来如下，其中用 fij表示在前 i 个小时有 j 点 hp 所能减的最大体 重。 fo
3、r(i=1;i=0;j-)/ j 表示在前 i 个小时还有 j 点 hp 时 if ( fi-1jfi-1j-hpi+wi ) 比较是吃还是不吃是最优 fij=fi-1j; 不吃的时候体重不变 else fij=fi-1j-hpi+wi; 吃的时候体重下降 优化空间复杂度 以上方法的时间和空间复杂度均为 O(N*V)，其中时间复杂度基本已经不能再优化了，但 空间复杂度却可以优化到 O(V)。具体如何实现，请同学们自己想办法解决。二：完全背包二：完全背包例例题题： ：纪纪老老师贴师贴膏膏药药粗心的张彦彬在上一讲中将纪老师得 hp 降到了 0，可怜的老师性命危在旦夕！同学们 必须采取紧急行动来挽救
4、纪老师的生命。李嘉浩同学飞快的将老师放上的担架，抬着老师 到了陈司义开的地精商店去贴膏药。商店里有 n 种膏药，有着不同的恢复力与价格。每种 膏药的库存量都很充足，但李嘉浩同学带的钱 m 却有限。请你设计方案将老师的 hp 升到 最高。 输入格式：第一行两个数 n，m 分别表示膏药种类和拥有钱的总数。第而行到第 n+1 每行 有两个数，分别表示膏药的价格和恢复 hp 的点数。 输出格式：输出一个数，即纪老师的 hp 的最大值。 输入样例： 4 200 10 1 20 90 99 10 201 8999 输出样例： 900 解析：完全背包与 01 背包唯一的不同就是每一种物品可以去无数次，如本题
5、中就写到膏药 的库存绝对充足，如果没有这句话完全背包就变成了 01 背包问题。也正是由于这一点导 致完全背包与 01 背包的解法惊人的相似。它的动态方程是 fij=maxfij,fij-ci+wi 发现没有，一模一样！那它的解法到底和 01 背包有什么不同呢？请看： for(i=1;ifi-1j-hpi+wi ) 比较是贴还是不贴是最优 fij=fi-1j; 不贴的时候 hp 不变 else fij=fi-1j-hpi+wi; 贴的时候 hp 上升 只是将 j 的循环循序颠倒了一下而已，为什么这样一改就可行呢？首先想想为什么 01 背包中要按照 j=HP.0 的逆序来循环。这是因为要保证第 i 次循环中的状态 fij是由状态 fi-1j-hpi递推而来。换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入 第 i 件物品”这件策略时，依据的是一个绝无已经选入第 i 件物品的子结果 fi-1j-hpi。 而现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第 i 种物品”这 种策略时，却正需要一个可能已选入第 i 种物品的子结果 fij-hpi，所以就可以并且必须 采用 j= 0.HP 的顺序循环。这就是这个简单的程序为何成立的道理。炉灰原创转载请注明出处
