java - 针对重量而不是值优化的背包算法

Question

是否可以修改 1-0 Knapsack 算法以优化袋中元素的最终总重量作为第一选择(以及值作为第二选择) ，保持相同的算法复杂度？

我正在研究 this java implementation (文末)

更具体地说，我正在考虑更改这段代码

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];
}

还有一些其他条件，首先控制权重是否接近阈值添加此项目，然后如果权重不变，则该值是否更好。

您知道如何在不改变复杂性的情况下做到这一点吗？

谢谢

编辑“首先控制重量是否接近阈值添加此项目”我的意思是达到背包的重量限制。换句话说，在不破坏包的情况下“最大化我可以携带的重量”

Answer 1

您是否正在尝试执行以下操作？选择元素，使重量最大化，同时仍遵守重量限制。如果存在多个最优解，每个最优解都达到最大可能的权重，则通过选择总值最大的解来从中进行选择。

如果是这样，那么我建议如下。 (我考虑的是背包问题本身，而不是您的 Java 实现。)

设 M = 所有项目中的最大值 [edited]，N = 项目数。用 weight + value/MN 替换每个值(在目标函数中)。

然后模型将最大化总重量，同时仍然遵守重量限制。如果有多个具有相同最佳权重的解决方案，它将选择具有最大值的一个。除以 MN 可确保您永远不会以更差的权重为代价选择具有更高值(value)的解决方案。