c - 背包变体？

Question

我搜索了这种类型的算法并红色了很多东西，但我找不到我正在寻找的东西。

所以，我要去购物，我有 x 的钱，我的卡车最多可以承受 y 的重量，而且每件商品都有一个奖励积分、一个重量和一个价格。输出应该给出可以获得的最大奖励积分，以使所选物品的总重量不超过卡车的容量和我必须花费的钱！

我可以在这里使用一些帮助，你知道算法的名称吗？我应该如何进行？我必须用C来做！

谢谢 ！！

Answer 1

你试过什么？

这些类型的问题通常属于优化或约束满足的范畴。

尝试为您的问题编写一个函数表达式，看看您是否可以使用简单的微积分或单纯形方法来解决它。

Answer 2

我知道背包问题的两种变体。0-1版本不能包含分数权重（取不取），比如我不能取次优的一半。另一个版本则相反，允许使用小数项。这个微小的差异非常显着，有利于分数版本。

分数版本可以通过贪心算法求解。您可以尽可能多地拿走最有价值的“单价”物品。重复直到你的卡车满了。

0-1 版本有点难，因为它不能通过简单的贪心算法来解决。例如，假设您的卡车可以承载 800 磅。我们可以从一个

1. 1 张重 500 磅、价值 1000 美元的桌子（单价 2 美元/磅）
2. 1 个长凳：重量 - 701 磅：价值 - 1577.25 美元：单位 2.25 美元/磅
3. 3 个书柜：重量 - 100 磅：价值 - 200 美元：单位 2 美元/磅

贪心算法的总价为 1577.25 美元。
最佳值是 3 个书柜，桌子 = 1600 美元。

如果以上是分数背包版本，那么只需花费 1775.25 美元的长凳和 99 磅的桌子/书柜。

在 0-1 的情况下，我们需要使用动态编程之类的东西来检查所有解决方案。

Answer 3

商品重量和商品价格是约束条件。奖励学分是目标。因此，您有一个多维背包问题（一个目标；两个约束）。众所周知的动态规划解决方案背包会泛化，但复杂度会随着约束的数量呈指数增长。