题目
版本一(二维数组)
思路
1.定义状态 dp[ i ][ j ] ,表示前i件物品，背包容量为j时的最优解。(局部最优解)
2.计算dp[ i ][ j ]时会现两种情况：背包容量不够，背包容量足够。
(1)背包容量不够：显然容量不够时就拿不了第i件物品，所以此时有dp[ i ][ j ] = dp[ i-1 ][ j ]。
(2)背包容量足够：此时会有两种先择，拿或不拿。
1）拿第i件物品，此时最优解为dp[ i ][ j ] =dp[ i-1 ][ j-v[ i ] ] + w[ i ] 。
2）不拿第i件物品，dp[ i ][ j ] = dp[ i-1 ][ j ]。
3）因为在做出的选择要使所拿物品价值最大
故dp[ i ][ j ] = max { dp[ i-1 ][ j-v[ i ] ] + w[ i ] ， dp[ i-1 ][ j ] }（状态转移方程式）
题解
在完成题目要求的输入时，为使物品与数组下标对应，在输入数组v和w中的值时从1开始
for (i = 1; i <= N; i++) { scanf("%d%d", &v[i], &w[i]); }
给dp数组初始化，没有物品时，无论背包容量有多大，能装最大价值物品都为0；背包容量为0时，无论有多少件物品都装不了东西
初始化过程如下：
//给dp数组初始化，没有物品时，无论背包容量有多大，能装最大价值物品都为0 for (i = 0; i <= V; i++) { dp[0][i] = 0; } //给dp数组初始化，背包容量为0时，无论有多少件物品都装不了东西 for (i = 0; i <= N; i++) { dp[i][0] = 0; }
核心过程如下：
int main() { int i, j; int N, V; scanf("%d%d", &N, &V); int v[1001], w[1001]; //为使物品与下标对应，所以输入时从1开始 for (i = 1; i <= N; i++) { scanf("%d%d", &v[i], &w[i]); } int dp[1001][1001]; //给dp数组初始化，没有物品时，无论背包容量有多大，能装最大价值物品都为0 for (i = 0; i <= V; i++) { dp[0][i] = 0; } //给dp数组初始化，背包容量为0时，无论有多少件物品都装不了东西 for (i = 0; i <= N; i++) { dp[i][0] = 0; } for (i = 1; i <= N; i++) { for (j = 1; j <= V; j++) { // 背包容量不足 if (j < v[i]) dp[i][j] = dp[i - 1][j]; // 背包容量足够，可进行选择 else dp[i][j] = fmax(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]); } } printf("%d", dp[i - 1][j - 1]); }
完整代码：
int main() { int i, j; int N, V; scanf("%d%d", &N, &V); int v[1001], w[1001]; for (i = 1; i <= N; i++) { scanf("%d%d", &v[i], &w[i]); } int dp[1001] = { 0 }; for (i = 1; i <= N; i++) { for (j = V; j >= 1; j--) { if (j >= v[i]) { dp[j] = fmax(dp[j - v[i]] + w[i], dp[j]); } } } printf("%d", dp[V]); }
版本二(一维数组)
上面的方法时间空间复杂度都为 O(N*V),时间复杂度很难继续优化。但是空间复杂度可以进一步优化。
思路
可以先看一看代码再看下面解析
（1）状态dp[ j ]定义：N件物品，背包容量 j 下的最优解。
（2）注意在次循环中枚举背包容量 j 必须从V开始。因为在用二维数组求解时会发现，算有前i件物品时的最优解的时候，只会与有前 i-1 件物品时的最优解有关，不会与有前 i-2 或者与有前 i+1件物品时有关。在使用一维数组求解时，当 i 更新了，数组内容仍然记录者之前的数据，随着 j 的更新，数组内容才会随着更新。在次循环中，若 j 正序，数组内容是从前往后更新的，而在计算dp[ j ]时正需要前面的数据，但是已经更新过找不到了。若 j 逆序，数组内容也是从后往前更新的，在计算dp[ j ]时，它前面的旧数据仍然存在，只有当旧数据被使用过后才会被更新。
（3）状态转移方程为：f[j] = max(f[j], f[j - v[i]] + w[i] ）。
代码
1. int main() 2. { 3. int i, j; 4. int N, V; 5. scanf("%d%d", &N, &V); 6. int v[1001], w[1001]; 7. for (i = 1; i <= N; i++) 8. { 9. scanf("%d%d", &v[i], &w[i]); 10. } 11. int dp[1001] = { 0 }; 12. for (i = 1; i <= N; i++) 13. { 14. for (j = V; j >= 1; j--) 15. { 16. if (j >= v[i]) 17. { 18. dp[j] = fmax(dp[j - v[i]] + w[i], dp[j]); 19. } 20. } 21. } 22. printf("%d", dp[V]); 23. }
在看完上面解析后，可以自己尝试这用两种方法解决该题目，题目链接：01背包问题
