是否有可能修改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];
}
在某些其他条件下，首先控制重量是否接近添加此项目的阈值，如果重量没有变化，则表示该值是否更好。
你有没有想过如何在不改变复杂性的情况下做到这一点？
谢谢
编辑“首先控制重量是否接近添加此项目的阈值”我的意思是达到背包的重量限制。换句话说，“最大化我可以随身携带的重量”而不会破坏它
你想做以下事吗？选择项目以使重量最大化，同时仍然遵守重量限制。如果有多个最优解决方案，每个解决方案都达到最大可能的权重，那么通过选择总价值最大的解决方案来选择它们。
如果是这样，那么我建议如下。 （我正在考虑背包问题本身，而不是你的Java实现。）
设M =所有项目中的[编辑]的最大值和N =项目数。用权重+值/ MN替换每个值（在目标函数中）。
然后模型将最大化总重量，同时仍然尊重重量限制。如果有多个具有相同最佳权重的解决方案，它将选择具有最大值的解决方案。除以MN确保您永远不会选择具有更好价值的解决方案而牺牲更重的重量。
我终于找到了专门针对我的问题的解决方案。
我使用了问题中链接的算法（this），但不考虑项目的值，我最大化重量（我已经使用重量作为重量和值）。所以他的背包算法优化了包中的重量，而没有考虑任何值。
为了最大化值，我按照desc顺序对项目进行了排序，从更大的值到更低的值，在计算算法的矩阵之前，并且在相同的值（在我的情况下是他的权重）的情况下，我不改变项目组成，因为第一项具有更大的值，因此第一组项具有更大的值。
它可能不是最好的解决方案，但似乎工作得很好（在我的情况下）。希望可以帮助
优化最终重量意味着什么？优化的重量对我来说似乎是一个空洞的包。
所以是的，它会通过使其变得微不足道而将复杂性改变为O（1）。
你能说出你的目标吗？
== ==编辑
嗨，如果同时最大化你的体重是你想要达到的目的，我们似乎在谈论一个dual problem。您可以研究线性规划和双重单纯形算法（参见Wiki）