1.本题是第一次遇到完全背包的动态规划问题，与01背包问题相比最大的不同就是每一个物品的数量从1变为了无穷。完全背包问题可以使用二维dp数组，更加直观易懂。行为物品列为最大重量，元素值为最大价值。递推公式的结构与01背包的一样，不同点在于如果选择放该物品，要从本行寻找减去该物品重量的元素值，而不是去上一行寻找，原因在于物品没有数量限制，剩余的空间不是从“没考虑当前物品”的上一层省出来的，而是从“可能已经放过当前物品”的本层省出来的。递推公式为：dp[i][j] = fmax(dp[i - 1][j], dp[i][j - weight[i]] + val[i])。

2.基于以上思想，可写出完整代码如下：

1. #include <stdio.h> 2. #include <math.h> 3. #include <string.h> 4. 5. int main(){ 6. // num：物品数量，max_weight：背包最大承重 7. int num, max_weight; 8. scanf("%d %d", &num, &max_weight); 9. 10. // weight[i]第i件物品重量，val[i]第i件物品价值 11. int weight[num], val[num]; 12. memset(weight, 0, sizeof(weight)); 13. memset(val, 0, sizeof(val)); 14. for (int i = 0; i < num; i++){ 15. scanf("%d %d", &weight[i], &val[i]); 16. } 17. 18. // dp[i][j]：前i件物品，背包容量j时的最大价值（完全背包二维数组） 19. int dp[num][max_weight + 1]; 20. for (int i = 0; i < num; i++){ 21. memset(dp[i], 0, sizeof(dp[i])); 22. } 23. // 初始化第一件物品：完全背包，同一物品可多次选取 24. for (int i = weight[0]; i <= max_weight; i++){ 25. dp[0][i] = dp[0][i - weight[0]] + val[0]; 26. } 27. 28. // 遍历剩余物品 29. for (int i = 1; i < num; i++){ 30. // 从小到大遍历容量，允许重复选取当前物品（完全背包核心） 31. for (int j = 0; j <= max_weight; j++){ 32. if (j < weight[i]){ 33. // 装不下，继承前i-1件的最优解 34. dp[i][j] = dp[i - 1][j]; 35. } else { 36. // 二选一：不选当前物品 / 重复选当前物品 37. dp[i][j] = fmax(dp[i - 1][j], dp[i][j - weight[i]] + val[i]); 38. } 39. } 40. } 41. 42. // 输出全部物品、背包满承重的最大价值 43. printf("%d", dp[num - 1][max_weight]); 44. 45. return 0; 46. }

该算法时间复杂度和空间复杂度均为O(num * max_weight)。

3.完全背包问题同样可以使用一维动态dp数组，与01背包相比唯一不同点在于完全背包的内层循环是正序，而01背包是逆序。01背包逆序是因为物品数量只有1个，需要防止物品被多次选取；而完全背包的物品数量是无限个，所以需要正序来保证物品能被多次选取。相当于物品数量的特点决定了使用哪种遍历顺序。

4.基于以上思想，可写出完整代码如下：

1. #include <stdio.h> 2. #include <math.h> 3. #include <string.h> 4. 5. int main(){ 6. // num：物品种类数，max_weight：背包最大载重 7. int num, max_weight; 8. scanf("%d %d", &num, &max_weight); 9. 10. // weight数组存每种物品重量，val数组存每种物品价值 11. int weight[num], val[num]; 12. memset(weight, 0, sizeof(weight)); 13. memset(val, 0, sizeof(val)); 14. for (int i = 0; i < num; i++){ 15. scanf("%d %d", &weight[i], &val[i]); 16. } 17. 18. // dp[j]：容量为j的背包可装入的最大价值 19. int dp[max_weight + 1]; 20. memset(dp, 0, sizeof(dp)); 21. 22. // 完全背包一维优化，物品可无限取用 23. for (int i = 0; i < num; i++){ 24. // 容量正序遍历，允许重复选取当前物品 25. for (int j = weight[i]; j <= max_weight; j++){ 26. // 不选当前物品dp[j] / 选当前物品dp[j-weight[i]]+val[i]，取更大值 27. dp[j] = fmax(dp[j], dp[j - weight[i]] + val[i]); 28. } 29. } 30. 31. // 输出满载背包的最大价值 32. printf("%d", dp[max_weight]); 33. 34. return 0; 35. }

该算法时间复杂度为O(num * max_weight)，空间复杂度均O(max_weight)。

5.在使用一维动态dp数组时，对于01背包问题，由于最后两层for循环的的内层循环时逆序的，所以两层for循环不能换位置，否则会引起逻辑错乱；而完全背包问题因为两层都是正序的，两层for循环可以互换位置。