背包问题将如何把这些重量放在一个袋子里，如下所示

Question

一次盗窃，抢劫一家商店，发现n件物品；ith元素价值vi美元，重量wi磅。他想尽可能带贵重的东西，但他的背包最多能带W磅。盗窃罪被允许拿走一个物品的重量的分数和价值的分数。确定他应该拿哪些物品？目标是在不超过背包重量限制W的情况下最大化物品的价值。项目1（价格=30$,重量=10kg),项目2（价格=100$,重量=25kg),项目3（价格=250$,重量=50kg),项目4（价格=30$,重量=30kg),项目5（价格=20$,重量=10kg),背包容量(W)=100kg

Answer 1

因为小偷可以拿一个项目的一小部分，拿一个重量的一部分，拿一个价值的一部分，所以你可以使用贪婪的算法。

按（value/weight）降序对（value，weight）对进行排序。然后简单地从这个列表中选择项目，直到您没有空间为止。