最大填充包的算法（這不是揹包0/1）

Question

我正在處理一些需要我解決以下算法問題的任務：

---

- 您有收集項目（它們的權重）：[ w1，w2，...，wn]
- 您有一個重量爲：W
的包 - 需要最大限度地填充包（儘可能多地填充）與給定項目的子集。

---

因此，這個不是「揹包0/1」的問題，因爲我們只處理權重（我們只有一個項目參數）。因此，我假設它可能有一個解決方案（揹包是NP-完全的）或某種算法給出了近似正確的結果。

請不要建議我「貪婪算法」，因爲我相信應該有一個算法，它會給出更好的結果。我認爲它應該是一個使用「動態編程」的算法。

預先感謝您:)

Answer 1

在這種特定情況下，你在袋子最小化的自由空間，因此考慮重量值獲得最大的收益。這個問題通常被稱爲subset sum problem，是揹包問題族的一個特例。

的DP關係如下所示

，其中每一步你試圖找到設置由先前的元素加上新元素

的最大值（不超過包包的容量）

C + +實現子集求和問題來回答這個問題「我可以完全填滿這些元素？」和驅動程序如下

bool ssp(const vector<int>& v, const int& N) { 

    vector<vector<int>> m(v.size() + 1 /* 1-based */, 
         vector<int>(N + 1 /* 1-based */, 0)); 

    // The line above also took care of the initialization for base 
    // cases f(i,0) = 0 and f(0,b) = 0 

    for (int i = 1; i <= v.size(); ++i) { // For each subset of elements 
    for (int b = 1; b <= N; ++b) { // For each subcapacity 
     int opt1 = m[i - 1][b]; 
     int opt2 = -1; 
     if (b - v[i - 1] >= 0) { // No caching to keep this readable 
     opt2 = m[i - 1][b - v[i - 1]] + v[i - 1]; 
     if (opt2 > b) 
      opt2 = -1; // Not allowed 
     } 
     m[i][b] = max(opt1, opt2); 
    } 
    } 

    return (m[v.size()][N] == N); 
} 

int main() { 

    const vector<int> v = { 1, 3, 7, 4 }; 
    const int N = 11; 

    cout << "Subset sum problem can be solved with the given input: " 
     << boolalpha << ssp(v, N); // true 

    return 0; 
} 

的複雜度爲O(N⋅I)其中I是在起始集合元素的數量。這是一個假多項式複雜性。

來源：Knapsack problem

Answer 2

實際上所描述的問題不在於0-1-Knapsack problem，而是一個特殊的情況下，其也被稱爲最大的子集和問題，這是desribed here。它是NP -complete，這意味着它不比0-1 -napshot複雜。這就是說，它可以通過任何旨在用於0-1-揹包問題的優化算法來解決，方法是將物品利潤設置爲等於其權重。總而言之，可以使用以下動態規劃算法來解決最優化問題; s[i]表示i第012項和m是整數值狀態空間時的大小，其中m[i,s]表示使用項目範圍{0,...i}中的項目可達到的最大值。

for j from 0 to W do: 
    m[0, j] := 0 

for i from 1 to n do: 
    for j from 0 to W do: 
     if s[i] > j then: 
      m[i, j] := m[i-1, j] 
     else: 
      m[i, j] := max(m[i-1, j], m[i-1, j-s[i]] + s[i]) 

正如他們原來的問題，提及以下貪婪算法產生一個2-近似，這是一種類似的算法的揹包問題的變形例。

1. select any subset of the items such that there is no other 
    item which can be feasibly chosen 
2. select the largest item 
3. out of 1. and 2., choose the subset which yields the larger total size