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循环可以互换位置。