没有重复的背包

Question

#include <iostream>
#include <vector>
#include <algorithm>
using std::vector;

int o_w(int W, const vector<int> &w) {
  vector<int> c(W+1);
  for (size_t i = 0; i < w.size(); ++i) {
      for(int j = W; j - w[i] >= 0; --j) {
            c[j] = std::max(c[j], c[j - w[i]] + w[i]);
      }
  }
  return c[W];
}

int opti_w(int W,const std::vector<int> &w,int n){
    std::vector<std::vector<int>> value(n+1,vector<int>(W+1,0));
    for(int i=0;i<=n;i++){
        for(int j=0;j<=W;j++){
            std::cout<<value[i][j]<<" ";
        }
        std::cout<<"\n";
    }

    for(int i=1;i<=n;i++){
      for(int j=1;j<=W;j++){
       //value[j][i]=std::max(value[j][i-1],value[j-w[i]][i-1]+w[i]);
      std::cout<<"i:"<<i<<" j:"<<j<<"\n";
      std::cout<<"value[i][j]:"<<value[i][j]<<"\n";
      std::cout<<"value[i-1][j]:"<<value[i-1][j]<<"\n";
      std::cout<<"w[i-1]:"<<w[i-1]<<"\n";
      std::cout<<"value[i-1][j-w[i-1]]:"<<value[i-1][j-w[i-1]]<<"\n";
      std::cout<<"value[i-1][j-w[i-1]]+w[i-1]:"<<value[i-1][j-w[i-1]]+w[i-1]<<"\n";
      value[i][j]=std::max(value[i-1][j],  value[i-1][j-w[i-1]] +w[i-1]  );
      }
    }
    
     for(int i=0;i<=n;i++){
        for(int j=0;j<=W;j++){
            std::cout<<value[i][j]<<" ";
        }
        std::cout<<"\n";
    }

    return value[n][W];
   // return value[W][n];
}

int main() {
  int n, W;
  std::cin >> W >> n;
  vector<int> w(n);
  for (int i = 0; i < n; i++) {
    std::cin >> w[i];
  }
  std::cout<<opti_w(W, w, n);
  //std::cout << o_w(W, w) << '\n';
}

在函数 opti_w 中，我以某种方式使用了错误的公式或出现错误，导致我无法获得正确的值，因为有时 j-[w-1] 变为负数，因此访问了不需要的元素。

函数o_w正确，可用于验证答案。

我该如何解决这个问题，解决方案中有什么不正确的地方。

Answer 1

你快到了。为什么不将 std::max 语句置于 if 条件下以处理 j-w[i-1] 毫无意义的情况？

Answer 2

for(int i=1;i<=n;i++){
   for(int j=1;j<=W;j++){
      value[i][j] = value[i-1][j];
      if(w[i-1]<=j){
       value[i][j]=std::max(value[i][j],  value[i-1][j-w[i-1]] +w[i-1]  );
       }
      }
    }

我只是更改了 if(w[i-1]<=j) 中的代码，它起作用了。

没有重复的背包

Knapsack without repetition

arrays

algorithm

knapsack-problem

dynamic-programming

multidimensional-array