07-问题分析

6.2.1　问题分析

n个物品和1个购物车，每个物品i对应价值为v_i，重量w_i，购物车的容量为W（你也可以将重量设定为体积）。每个物品只有一件，要么装入，要么不装入，不可拆分。如何选取物品装入购物车，使购物车所装入的物品的总价值最大？

我们可以尝试贪心的策略：

（1）每次挑选价值最大的物品装入背包，得到的结果是否最优？

（2）每次挑选所占空间最小的物品装入，能否得到最优解？

（3）每次选取单位重量价值最大的物品，能否得到价值最高？

思考一下，如果选价值最大的物品，但重量非常大，也是不行的，因为运载能力有限，所以第（1）种策略舍弃；如果选所占空间最小的物品装入，占用空间小不一定重量就轻，也有可能空间小，特别重，所以不能在总重限制的情况下保证价值最高，第（2）种策略舍弃；而第（3）种是每次选取单位重量价值最大的物品，也就是说每次选择性价比最高的物品，如果可以达到运载重量m，那么一定能得到价值最高？不一定。因为物品不可分割，有可能存在购物车没装满，却不能再装剩下的物品，这样价值不一定达到最高。

因此采用贪心策略解决此问题不一定能得到最优解。

我们可以先用普通队列式分支界限法求解，然后在6.3.6节中用优先队列式分支界限法求解，大家可以对比体会有何不同。