求解揹包概率與「最小值」約束在每個項目上

Question

每個項目有三個屬性

• 的項目的大小S _我
• 項v的值_我
• 將物品加入揹包所需的最小值M _i（< = 10 ）

這將是最多100個項目。

我們給出了揹包K的大小（K < = 1000）和初始值V（在揹包中沒有空間）。
的項「I」可以被放入揹包，當且僅當M _我小於或等於V.
用V _我添加在揹包V增加的項目之後。
我們必須最大化放入給定尺寸揹包的物品數量（而不是價值）。

我找到了this question這與之相似。但是在答案中描述的算法是立方時間，對於這個問題來說速度不夠快。我們如何以更好的方式解決這個問題？

Answer 1

我可以在這裏給出一個O（n^3）算法。我不知道這個問題是否可以進一步優化爲O（n^2）。

首先，這個問題是如果物品數量最大化，這與其他揹包問題有點不同。同時，它也有一個限制，即只有當揹包的總價值大於其自身價值時才能選擇單個項目。因此，一個明顯的推論是，在選擇相同數量的物品和固定總尺寸的情況下，總值應儘可能大（以便可以將更多物品添加到揹包中）。請注意，項目n的數量（< = 100）和揹包K的大小（< = 1000）不是很大，設f [i] [j]表示選擇i項目時的最大值大小j。最初，除了f [0] [0] = V之外，所有f [i] [j]都被設置爲0。

然後根據添加所需的最小值對項目進行排序。這是一個貪婪的想法，因爲在分類之後，我們只能遍歷每個項目一次。

的DP方法看起來像如下：

for (int k=0;k<n;k++) //iterate items 
    for (int i=n;i>=0;i--) 
     for (int j=K;j>=0;j--) if (item.M[k]<=f[i][j]) 
      f[i+1][j+item.S[k]]=max(f[i+1][j+item.S[k]],f[i][j]+item.V[k]); 

和最終的答案（的最大項目數）爲：

for (int i=n;i>=0;i--) 
    for (int j=0;j<=K;j++) 
     if (f[i][j]) return i;