动态规划-----完全背包问题

完全背包问题

​​https://www.acwing.com/problem/content/3/​​

与01背包不同的是，每个物品可以选取无穷多个。因此思考方式可以在01背包的基础上进行调整，把选择该物品的状态划分继续细分即可。

朴素O(n^3)代码：

int dp[1005][1005], w[1005], v[1005];
void solve(){
  int N, V;
  cin >> N >> V;
  for(int i = 1; i <= N; i ++) cin >> v[i] >> w[i];
  
  for(int i = 1; i <= N; i ++){
    for(int j = 0; j <= V; j ++){
      dp[i][j] = dp[i - 1][j];
      for(int k = 1; k * v[i] <= j; k ++){
        dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]);
      }         //此处是dp[i][j]
      
    }
  }
  cout << dp[N][V];

可以把不选归纳到k=0的情况。

k=0时，dp[i][j] = max(dp[i][j], dp[i-1][j-0] + 0);

void solve(){

  int N, V;
  cin >> N >> V;
  for(int i = 1; i <= N; i ++) cin >> v[i] >> w[i];
  
  for(int i = 1; i <= N; i ++){
    for(int j = 0; j <= V; j ++){
      for(int k = 0; k * v[i] <= j; k ++){
        dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]);
      }
      
    }
  }
  cout << dp[N][V];

}

但是！这样做会超时！

需要考虑优化。

void solve(){

  int N, V;
  cin >> N >> V;
  for(int i = 1; i <= N; i ++) cin >> v[i] >> w[i];
  
  for(int i = 1; i <= N; i ++){
    for(int j = 0; j <= V; j ++){
      dp[i][j] = dp[i - 1][j];
      if(j >= v[i])
        dp[i][j] = max(dp[i][j], f[i][j - v[i]] + w[i]);
    }
  }
  cout << dp[N][V];

}