针对重量优化的背包算法，而非价值

Question

有没有可能修改01背包算法以优化袋子中物品的最终总重量作为首选（并将价值作为次要选择），同时保持相同的算法复杂度？

我正在使用这个Java实现（在文章末尾）。

更具体地说，我想要修改以下代码段：

if (wt[item-1]<=weight){
    V[item][weight]=Math.max (val[item-1]+V[item-1][weight-wt[item-1]], V[item-1][weight]);
}else{
    V[item][weight]=V[item-1][weight];
}

以下是您需要翻译的内容：

带有其他条件，首先控制物品重量是否接近阈值，然后确定如果重量不变，是否价值更高。

您有想法如何在不改变复杂性的情况下完成此操作吗？

谢谢

编辑“首先控制物品重量是否接近阈值，然后添加该物品”是指达到背包的重量限制。换句话说，“尽可能多地携带重量而不破坏背包”

- Ve9

---

如果您将每个项目的值更改为等于其重量，那么它找到的解决方案会发生什么？如果您将这些值中的每一个乘以某个大数，会发生什么？现在您是否可以看出如何说服它更喜欢选择原始价值较高的项目了？ - j_random_hacker

Answer 1

你是否想要完成以下任务？选择物品使得总重量最大，同时保证不超过重量限制。如果有多个最优解使得总重量达到最大值，则选择其中拥有最大总价值的解。

如果是这样，我建议如下操作（我考虑的是背包问题本身，而非其Java实现）。

令M为所有物品价值中的最大值，令N为物品个数。将目标函数中的每个价值替换为权重加上价值除以MN。

这样模型会最大化总重量，同时保证不超过重量限制。如果存在多个相同最优重量的解，则会选择拥有最大总价值的解。除以MN可以确保您永远不会通过减少重量来换取更高的价值。

- LarrySnyder610

---

是的，这就是我一直在寻找的解决方案！它运行得非常好，谢谢！ - Ve9

抱歉@grendelsdad，我认为M应该是“所有项目的最大值”。我对吗？ - Ve9

是的，我认为你是对的，但在我编辑答案之前，让我问一下——所有的权重都是整数吗？如果不是，我需要进行另一种修改。 - LarrySnyder610

Answer 2

我终于找到了一个专门解决我的问题的解决方案。

我使用了在问题中链接的算法（这里），但是与考虑物品价值不同，我最大化重量（我将重量用作重量和价值）。因此，背包算法优化袋子中的重量，而不考虑价值。

为了最大化价值，在计算算法矩阵之前，我按降序对项目进行了排序，从更高的价值到更低的价值，并且如果具有相同的价值（在我的情况下是重量），则不更改项目组成，因为第一批项目具有更高的价值，因此第一批项目具有更高的价值。

这可能不是最好的解决方案，但在我的情况下似乎效果很好。希望能有所帮助。

- Ve9

---

@grendelsdad 的解决方案很棒，但它并不适用于我的特定情况。无论如何，这仍然是最佳答案。 - Ve9

感谢分享。您的解决方案很直观易懂。 - ng.newbie

Answer 3

优化最终权重是什么意思？对我来说，优化后的权重似乎是一个空袋子。

所以，通过使其变得微不足道，它将改变复杂度为O（1）。

你能具体说明你的目标吗？

==编辑==

嗨，如果您同时尝试最大化您的重量，那么我们正在谈论一个双重问题。您可以研究线性规划和对偶单纯形算法（请参见Wiki）。

- Dennis

---

嗨，"首先控制物品的重量是否接近阈值，然后再添加该物品"，我指的是达到背包的重量限制。换句话说，就是在不破坏背包的情况下最大化我能携带的重量。谢谢。 - Ve9