状态转移方程

初始的状态转移方程

  1. for(int i = 0; i <= n; i++){
  2.     for(int v = w[i]; v <= V; v++){
  3.         dp[i][v] = max(dp[i - 1][v], dp[i - 1][v - w[i]] + c[i]);
  4.     }
  5. }

利用滚动数组压缩空间(必须要逆序)

  1. for(int i = 0; i <= n; i++){
  2.     for(int v = V; v >= w[i]; v--){
  3.         dp[v] = max(dp[v], dp[v - w[i]] + c[i]);
  4.     }
  5. }

输出过程代码

输入
5 8
3 5 1 2 2
4 5 2 1 3
输出：dp[8] ~ dp[1]
i = 1，4 4 4 4 4 4 0 0
i = 2, 9 5 5 5 4 4 0 0
i = 3, 9 7 7 6 6 4 2 2
i = 4, 9 7 7 6 6 4 2 2
i = 5, 10 9 9 7 6 5 3 2

  1. #include<cstdio>
  2. #include<algorithm>
  3. using namespace std;
  4. const int maxn = 100;
  5. const int maxv = 1000;
  7. int w[maxn], c[maxn], dp[maxv];//w重量、c价值
  8. int main(){
  9.     int n, V;//V是容量,n是物品数量
  10.     scanf("%d%d", &n, &V);
  11.     for(int i = 1; i <= n; i++) scanf("%d", &w[i]);
  12.     for(int i = 1; i <= n; i++) scanf("%d", &c[i]);
  13.     for(int v = 0; v <= V; v++) dp[v] = 0;
  14.     for(int i = 1; i <= n; i++){
  15.         for(int v = V; v >= w[i]; v--){
  16.             dp[v] = max(dp[v], dp[v - w[i]] + c[i]);
  17.             printf("v = %d, dp[%d] = %d ", v, v, dp[v]);
  18.         }
  19.         printf("\n");
  20.         for(int i = V; i >= 1; i--) printf("%d ",dp[i]);
  21.         printf("\n");
  22.     }
  23. }

题解代码

  1. #include<cstdio>
  2. #include<algorithm>
  3. using namespace std;
  4. const int maxn = 100;
  5. const int maxv = 1000;
  7. int w[maxn], c[maxn], dp[maxv];//w重量、c价值
  8. int main(){
  9.     int n, V, ans = 0;//V是容量,n是物品数量
  10.     scanf("%d%d", &n, &V);
  11.     for(int i = 1; i <= n; i++) scanf("%d", &w[i]);
  12.     for(int i = 1; i <= n; i++) scanf("%d", &c[i]);
  13.     for(int v = 0; v <= V; v++) dp[v] = 0;
  14.     for(int i = 1; i <= n; i++){
  15.         for(int v = V; v >= w[i]; v--){
  16.             dp[v] = max(dp[v], dp[v - w[i]] + c[i]);
  17.             ans = max(ans, dp[v]);
  18.         }
  19.     }
  20.     printf("%d", ans);
  21. }