背包：一个约束，每个物品只能选择一次，物品数量较多

Question

到目前为止，我的想法是生成一个超重的背包，然后递归地向后工作，一次替换一个项目，直到它<=最大重量。对于生成最优背包来说，这不是一个问题，然而，我真的想生成以下100个左右的背包。我想我可以通过继续我的递归过程来做到这一点，然而，我觉得这并不完全准确，因为a可能缺少稍微更优化的背包。

Answer 1

这个问题可以表述为一个整数程序。

maximize sum_{i in items} v_i * x_i
subject to
sum_{i in items} x_i <= 10       [u]
sum_{i in items} w_i * x_i <= W  [z]
for all i in items, x_i in {0, 1}  [y_i]

有许多求解器库将为您解决这个程序；或者，您可以自己做分支和绑定。这是对偶线性规划，求解它可以得到整数规划的目标值的一个上界，这是分枝定界所需要的。

minimize 10 * u + W * z + sum_{i in items} y_i
subject to
for all i in items, u + w_i * z + y_i >= v_i  [x_i]
u >= 0
z >= 0
for all i in items, y_i >= 0

给定z的值，设置其他变量就是通过v_i-w_i*z将正的y_i赋给九个最大的项，同时将u赋给第十个最大的值。应该可以三进制搜索zO(n log n)。