背包：一个约束，每个项目只能选择一次，有大量的项目

Question

我正在写一个算法，采取背包问题的形式。我试图在给定最大重量（W）的情况下使我的背包的价值（V）最大化。这些渔获物是每个物品（I）只能被选择一次，不论重量的背包只能容纳10件物品，并且有大量物品（500+）。

到目前为止，我的想法是生成背包超重，递归地逐步向后取代一个项目，直到它是< =最大重量。这对于生成最理想的背包不是问题，但是，我真的很想生成以下100个左右的背包。我想我可以通过继续我的递归过程来做到这一点，但是，我不觉得这是完全准确的，因为它可能缺少稍微更理想的背包。

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] 

有许多求解器库可以为你解决这个程序;或者，您可以自己完成branch and bound。这里是双线性程序，可以通过求解来获得整数程序的目标值的上限，这是分支和边界所需要的。

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是第十最大价值的问题。应该可以在时间O(n log n)三元搜索z。