algorithm - 背包算法变量

Question

我遇到的问题如下:
假设我有一个给定重量的存钱 jar ，我用一组给定的硬币在里面存钱。最后，我知道存钱 jar 的总重量以及我使用的硬币的重量和值(value)。

我想找出我可以保证存入存钱 jar 的最低金额，即最坏的情况。例如，如果:

• 总重量 = 100
• 使用的硬币重量 = {1, 50}
• 硬币的值(value) = {1, 30}

那么我能保证的银行最低值是60。

问题是背包变体，但我找不到正确的重复出现。

提前致谢!

Answer 1

我采用的方法是评估集合中的每一枚硬币，以确定其“值(value)密度”(需要一个更好的术语)——值(value)除以重量。在您的示例中，第一个硬币的值(value)密度为 1，第二个硬币的值(value)密度为 30/50 = 0.6。

然后从总重量为零开始，在不超过给定重量的情况下尽可能使用最低的“值(value)密度”硬币。然后应用下一个“值(value)密度”最低的硬币，依此类推，直到达到给定的重量。

这基本上是一种贪心算法。