第四讲：背包问题.pptVIP

第四讲 背包问题 1、问题描述 给定一组物品，每种物品都有自己的重量和价格(价值)，在限定的总重量范围内，我们如何选择，才能使得物品的总价值最高。 问题名称的来源 人类是一种贪婪的动物，如果给您一个容量一定的背包和一些大小不一的物品，裝到背包里面的物品就归您，遇到这种好事大家一定不会错过，用力塞不一定是最好的办法，用脑子才行。 另一个版本：人类是一种贪婪的动物，如果给您一些重量不一、价值不一的物品，只要您一次性扛得走就归您。 问题的抽象化 已知背包容量为w，n件物品，物品的重量依次为wi，物品的价格依次为pi，如何选取一部分物品，使其重量之和不超过w，而价格之和最大。 2、解决问题的自然思路 取不取第一件物品？(W1 W 则显然不取) 假定取了第一件物品，则剩下的事情可以表述为：已知背包容量为W ( 即W - W1 ) ，n-1件物品，物品的重量和价格已知，如何选取一部分物品，使其重量之和不超过W ，而价格之和最大。(以下简称为问题A) 假定不取第一件物品，则剩下的事情可以表述为：已知背包容量为W ，n-1件物品，物品的重量和价格已知， 如何选取一部分物品，使其重量之和不超过W ，而价格之和最大。(以下简称为问题B) 假定A问题已经解决，所选物品的价格之和为PA；假定B问题已经解决，所选物品的价格之和为PB。如果 PA+P1 PB 我们不取第一件物品，否则就取。 问题A、问题B与原来的问题性质完全相同，复杂度有所降低；再次分别展开这两个问题，性质也完全相同，复杂度再次降低；分解到最后，必然只有一件物品要考虑。 这启发我们，解决规模较大的问题，可以先分解，解决规模较小的问题；继而再分解，解决规模更小的问题；直到不需要再分解；然后回过头来解决之前的问题。这种思路被称之为“递归” 3、类属性设计 问题领域有哪些对象? 背包、物品 class Bag class Thing public class Thing { public final int weight ; public final int price ; public Thing(int weight, int price) { this.weight = weight; this.price = price; } } public class Bag { public final int capacity ; private VectorThing things = new VectorThing() ; public Bag(int capacity) { this.capacity = capacity; } public int getTotalWeight(){ int result =0; for(int i=0;ithings.size();i++) result += things.get(i).weight ; return result; } public int getTotalValue(){ int result =0; for(int i=0;ithings.size();i++) result += things.get(i).price ; return result; } public void place(Thing thing) { ... } } public void place(Thing thing) { if (isExist(thing)) throw new Error(同一件物品只允许取放一次); if (!canPlace(thing)) throw new Error(背包放入当前物品将会超出容量); things.add(thing); } private boolean canPlace(Thing thing) { return getRemainingCapacity()=thing.weight; } private boolean isExist(Thing thing) { for(int i=0;ithings.size();i++) if (things.get(i)==thing) return true ; return false; } private int getRemainingCapacity() { return capacity - getTotalWeight(); } 观察代码 Version0