動態規劃矩陣填補揹包

Question

如果我有以下限制：

values = {$1,$2,$3,$4} 
items = {blue,yellow,green,red} 
weights = {1,2,3,4} 
capacity = 4 

，我想如實填寫本人矩陣與代表項的權重的列和代表項目的數量選擇行：

 1  2  3 4  

1  $1  $1 $1 $1 
     {1} {1} {1} {1}  
2  $1  $1 $3  $3 
     {1} {1} {1,2} {1,2} 
3  $1  $1 $3  $3  
     {1} {1} {1,2} {1,2} 
4  $1  $1 $3  $3  <--- should be 4? 
     {1} {1} {1,2} {1,2} 

我期待看到的是，提供4作爲爲正確的金額，但我得到的解決方案。大括號{}中的數字代表一個基於的索引來查找這些項目。我在哪裏出錯了我的矩陣填充？

Answer 1

該解決方案是這樣的

#include <iostream> 
#include <string> 
#include <vector> 
#include <algorithm> 
using namespace std; 

// m[a][b] = NOWAY => There's no way to represent 
// weight `b` with first `a` items 
const int NOWAY = -1; 
typedef vector<vector<int>> vvi; 

const int values[] = {1, 2, 3, 4}; 
const string items[] = {"blue", "yellow", "green", "red"}; 
const int weights[] = {1, 2, 3, 4}; 
const int capacity = 4; 
const int itemcount = 4; 

void rec(vvi const & m, int represent, int mx, vvi & sol); 

int main() { 
    // m[i][j] -- total value 
    // i -- items 1..i were taken 
    // j -- total weight of those items 
    vvi m(itemcount + 1, vector<int>(capacity + 1, NOWAY)); 

    // No items weight nothing. The other values we're yet to build 
    m[0][0] = 0; 
    for (int i = 1; i <= itemcount; ++i) { 
     m[i] = m[i - 1]; 
     int w = weights[i - 1]; 
     // Find new representations 
     for (int j = capacity - w; j >= 0; --j) { 
      if (m[i][j] != NOWAY) { 
       m[i][j + w] = max(m[i][j + w], m[i][j] + values[i - 1]); 
      } 
     } 
    } 
    // Output table 
    for (int i = 0; i <= itemcount; ++i) { 
     for (int j = 0; j <= capacity; ++j) 
      m[i][j] == NOWAY ? cout << "x " : cout << m[i][j] << ' '; 
     cout << endl; 
    } 
    cout << endl; 
    // Find the index of the best solution (it's always in the last row) 
    int mxi = 0; 
    for (int i = 1; i <= capacity; ++i) 
     if (m.back()[mxi] < m.back()[i]) 
      mxi = i; 
    // Recurse to get all the representations 
    vvi solutions; 
    rec(m, mxi, itemcount, solutions); 
    // Output them 
    for (int i = 0, ilen = solutions.size(); i < ilen; ++i) { 
     cout << '{'; 
     bool f = true; 
     for (int j = 0, jlen = solutions[i].size(); j < jlen; ++j) { 
      if (!f) cout << ", "; 
      cout << items[solutions[i][j]]; 
      f = false; 
     } 
     cout << "}" << endl; 
    } 
} 

vector<int> path; 
void rec(vvi const & m, int represent, int mx, vvi & sol) { 
    if (represent == 0) { 
     sol.push_back(path); 
     return; 
    } 
    if (mx <= 0) return; 
    for (int i = mx - 1; i >= 0; --i) { 
     if (represent < weights[i]) 
      continue; 
     if (m.back()[represent - weights[i]] == m.back()[represent] - values[i]) { 
      path.push_back(i); 
      rec(m, represent - weights[i], i, sol); 
      path.pop_back(); 
     } 
    } 
} 

它返回

0 x x x x 
0 1 x x x 
0 1 2 3 x 
0 1 2 3 4 
0 1 2 3 4 

{red} 
{blue, green} 

（順便說一句，考慮在USACO或Topcoder培訓。）