09-完美图解

选择背景色：黄橙洋红淡粉水蓝草绿白色选择字体：宋体黑体微软雅黑楷体选择字体大小：小中大特恢复默认

我们现在假设这批古董如图2-4所示。

图2-4　古董图片

每个古董的重量如表2-1所示，海盗船的载重量c为30，那么在不能打碎古董又不超过载重的情况下，怎么装入最多的古董？

表2-1　古董重量清单

| 重量w[i] | 4 | 10 | 7 | 11 | 3 | 5 | 14 | 2 || :----- | :----- | :----- | :----- | :----- | :----- | :----- | :----- | :----- | :----- | :----- |

（1）因为贪心策略是每次选择重量最小的古董装入海盗船，因此可以按照古董重量非递减排序，排序后如表2-2所示。

表2-2　按重量排序后古董清单

| 重量w[i] | 2 | 3 | 4 | 5 | 7 | 10 | 11 | 14 || :----- | :----- | :----- | :----- | :----- | :----- | :----- | :----- | :----- | :----- | :----- |

（2）按照贪心策略，每次选择重量最小的古董放入（tmp 代表古董的重量，ans 代表已装裁的古董个数）。

i=0，选择排序后的第1个，装入重量tmp=2，不超过载重量30，ans =1。

i=1，选择排序后的第2个，装入重量tmp=2+3=5，不超过载重量30，ans =2。

i=2，选择排序后的第3个，装入重量tmp=5+4=9，不超过载重量30，ans =3。

i=3，选择排序后的第4个，装入重量tmp=9+5=14，不超过载重量30，ans =4。

i=4，选择排序后的第5个，装入重量tmp=14+7=21，不超过载重量30，ans =5。

i=5，选择排序后的第6个，装入重量tmp=21+10=31，超过载重量30，算法结束。

即放入古董的个数为ans=5个。