无法实现子集和的伪代码

Question

所以我正在尝试实现以下伪代码，但它不会像预期的那样工作。这是幻灯片中的问题描述，"Given an integer bound, "W"，以及 "n" 个项目的集合，每个项目的权重为正整数 "wi"，找到项目的子集 S：最大化 Sigma sub i 其中 i 是 S "wi" 的一个元素，同时保持此总和小于或等于或等于 W。我将附上以下幻灯片，说明我从中获取问题描述和伪代码的位置。我的实现问题是它只会找到总最大值而不是小于或等于重量的值。例如，如果我有重量 10 (W = 10) 和项目 3 (n = 3)，项目重量为 1， 4, & 8 那么下面的答案应该是 9；但是，我的解决方案给出了 12。这是幻灯片（*请注意，它说 w[j] 的地方应该是 w[i] - 幻灯片有错字):

这是我实现伪代码的代码：

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int max(int a, int b, int c) {
             if (a >= b)
                return a;
             else
                return b;       
          }

int optimal_weight(int W, const vector<int> &wt, int n){
    vector<vector<int> > M;
    M.resize(n+1);
    for(int i = 0; i < n+1; ++i){
        M[i].resize(W+1);
    }
    for(int w = 0; w < W+1; w++){
        M[0][w] = 0;
    }
    for(int i = 1; i < n+1; i++){
        M[i][0] = 0;
    }

for(int i = 1; i < n+1; i++){
    for(int w = 0; w < W+1; w++){
        if(wt[i] > w){
            M[i][w] = M[i-1][w];
        }

        M[i][w] = max(M[i-1][w], wt[i] + M[i-1][W-wt[i]], W);
    }
}



   for (int i = 0; i <= n; i++)
     {
       for (int j = 0; j <= W; j++)
          printf ("%4d", M[i][j]);
       printf("\n");
     } 

    return M[n][W];
} 

int main()
{
    //int val[] = {1, 1, 1};
    int W;
    int n;
    cin >> W >> n;
    vector<int> wt(n);
    for(int i = 0; i < n; i++){
        cin >> wt[i];
    }
    cout << optimal_weight(W, wt, n) << endl;

}

感谢您的帮助！

Answer 1

我想通了！这是我的解决方案：

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

using std::vector;

int optimal_weight(int W, const vector<int> &wt) {
  //write your code here

  int n = wt.size();
  vector<vector<int> > matrix;
  matrix.resize(W+1);
for(int i = 0; i < W+1; i++){
    matrix[i].resize(n);
}
  for(int j = 0; j < n; j++){
      matrix[0][j] = 0;
  }
    for(int w = 0; w < W + 1; w++){
      matrix[w][0] = 0;
  }
  for(int i = 1; i < n; i++){
      for(int w = 1; w < W+1; w++){
          matrix[w][i] = matrix[w][i-1];
          if(wt[i] <= w){
              //cout << wt[i] << endl;
              int val = matrix[w-wt[i]][i-1] + wt[i];
              if(matrix[w][i] < val){
                  matrix[w][i] = val;
              }
          }
      }
  }

  return matrix[W][n-1];


}

int main() {
  int n, W;
  std::cin >> W >> n;
  vector<int> wt(n+1);
  for (int i = 1; i < n+1; i++) {
      wt[0]=0;
    std::cin >> wt[i];
  }
  std::cout << optimal_weight(W, wt) << '\n';
}

无法实现子集和的伪代码

Having trouble implementing pseudocode for Subset Sum

c++

algorithm

dynamic

subset-sum

c++14