01 有多个物品，每个物品要么选，要么不选。 每个物品有不同的体积和价值 要在n个物品里面，选择总体积不超过背包体积V的，求最大价值是多少？ dp[i][j] 前i个物品中，体积最多为j的时候，最大价值为dp[i][j]; dp[i][j] = dp[i-1][j]; dp[i][j] = dp[i-1][j-c[i]] + w[i];

dp[i][j] = max(dp[i-1][j], dp[i-1][j-c[i]]+w[i]);

for(int j = V; j >= c[i]; j --);

dp[j] = max(dp[j], dp[j-c[i]]+w[i]);

多重背包 有n个物品，每个物品有N[i],第i个物品的体积为ci,价值为wi; 要在n个物品里面，选择总体积不超过背包体积V的，求最大价值是多少？ dp[i][j] 前i个物品中，体积最多为j的时候，最大价值为dp[i][j]; for (int k = 0; k <= N[i]; k ++) dp[i][j] = max(dp[i][j], dp[i-1][j-kc[i]]+kw[i]);

for(int j = V; j >= kc[i]; j --) dp[j] = max(dp[j], dp[j-kc[i]]+k*w[i]);

完全背包 有n个物品，每个物品有无限个,第i个物品的体积为ci,价值为wi; 要在n个物品里面，选择总体积不超过背包体积V的，求最大价值是多少？ dp[i][j] 前i个物品中，体积最多为j的时候，最大价值为dp[i][j];

for (int k = 0; kc[i] <= j; j++){ dp[i][j] = max(dp[i][j], dp[i-1][j-kc[i]]+w[i]); } O(n^3) dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i],dp[i-1][j-2c[i]]+2w[i],dp[i-1][j-3c[i]]+3w[i].... dp[i-1][j-kc[i]]+kw[i]); dp[i][j-c[i]]+w[i]=max(dp[i-1][j-c[i]]+w[i], dp[i-1][j-2c[i]]+2w[i],dp[i-1][j-3c[i]]+3w[i]... dp[i-1][j-kc[i]]+kw[i]);

O(n^2) dp[i][j] = max(dp[i-1][j],dp[i][j-c[i]]);

for (int j = c[i]; j <= V; j ++) dp[j] = max(dp[j], dp[j-c[i]]);

分组背包 有n个物品，分成了K组，每一组只能选择一种物品，每组每个物品的体积为c[k][i] ，价值w[k][i]; 要在n个物品里面，选择总体积不超过背包体积V的，求最大价值是多少？ dp[i][j]; 前i组物品中，体积最多为j的时候，最大价值为dp[i][j];

for i 1 ~ K for j 1 ~ V for(k = 0; k < n[i];k ++){ dp[i][j] = max(dp[i-1][j],dp[i-1][j-c[i][k]]+w[i][k]); }

for (int j = V; j >= c[i][k]; j --){ dp[j] = max(dp[j], dp[j-c[i][k]]+w[i][k]); }

01-多重-分组 空间优化体积都是倒着来 完全背包 空间体积优化是正着的。