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