16-完美图解

2.3.3　完美图解

假设现在有一批宝物，价值和重量如表 2-3 所示，毛驴运载能力 m=30，那么怎么装入最大价值的物品？

| 宝物i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | | :----- | :----- | :----- | :----- | :----- | :----- | :----- | :----- | :----- | :----- | :----- | :----- | :----- | | 重量w[i] | 4 | 2 | 9 | 5 | 5 | 8 | 5 | 4 | 5 | 5 | | 价值v[i] | 3 | 8 | 18 | 6 | 8 | 20 | 5 | 6 | 7 | 15 |

（1）因为贪心策略是每次选择性价比（价值/重量）高的宝物，可以按照性价比降序排序，排序后如表2-4所示。

| 宝物i | 2 | 10 | 6 | 3 | 5 | 8 | 9 | 4 | 7 | 1 | | :----- | :----- | :----- | :----- | :----- | :----- | :----- | :----- | :----- | :----- | :----- | :----- | :----- | | 重量w[i] | 2 | 5 | 8 | 9 | 5 | 4 | 5 | 5 | 5 | 4 | | 价值v[i] | 8 | 15 | 20 | 18 | 8 | 6 | 7 | 6 | 5 | 3 | | 性价比p[i] | 4 | 3 | 2.5 | 2 | 1.6 | 1.5 | 1.4 | 1.2 | 1 | 0.75 |

（2）按照贪心策略，每次选择性价比高的宝物放入：

第1次选择宝物2，剩余容量30−2=28，目前装入最大价值为8。

第2次选择宝物10，剩余容量28−5=23，目前装入最大价值为8+15=23。

第3次选择宝物6，剩余容量23−8=15，目前装入最大价值为23+20=43。

第4次选择宝物3，剩余容量15−9=6，目前装入最大价值为43+18=61。

第5次选择宝物5，剩余容量6−5=1，目前装入最大价值为61+8=69。

第6次选择宝物8，发现上次处理完时剩余容量为1，而8号宝物重量为4，无法全部放入，那么可以采用部分装入的形式，装入1个重量单位，因为8号宝物的单位重量价值为1.5，因此放入价值1×1.5=1.5，你也可以认为装入了8号宝物的1/4，目前装入最大价值为69+1.5=70.5，剩余容量为0。

（3）构造最优解

把这些放入的宝物序号组合在一起，就得到了最优解（2，10，6，3，5，8），其中最后一个宝物为部分装入（装了8号财宝的1/4），能够装入宝物的最大价值为70.5。