《算法设计与分析》上机实验报告(4)

专业和班级 实验名称 姓名 学号 成绩 0-1背包问题 1. 理解算法设计的基本步骤和各步的主要内容，基本要求 实验目的和求 2. 加深对回溯法基本思想的理解 3.培养学生用计算机解决实际问题的能力 1.掌握0-1背包问题的基本算法及其应用 实验任务 2. 利用回溯法找出具体问题的最优解 3. 分析实验结果，总结算法的时间和空间复杂度 1. 0-1背包问题描述 给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 2. 算法的设计思想： 这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。 用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是： f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]} 这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是实验步骤 f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。 3. 算法正确性证明

使用回溯法最重要的是要确定约束函数和限界函数，只有这样才能确定需要减去哪些枝节，否则解空间太大，根本无法解决。

在此问题中，首先我们可以看出，该问题的约束函数为： 如果当前背包中的物品的总容量是cw，前面的k-1件物品都已经决定好是否要放入包中，那么第k件物品是否放入包中取决于不等式

cw + wk <= M (其中，wk为第k件物品的容量，M为背包的容量)（此即约束条件）

然后我们再寻找限界函数，这个问题比较麻烦，我们可以回忆一下背包问题的贪心算法，即物品按照 物品的价值/物品的体积 来从大到小排列，然后最优解为

（1，1，1.......，1，t，0，0，......），其中0<=t<=1； 因此，我们在确定第k个物品到底要不要放入的时候(在前k-1个物品已经确定的情况下)，我们可以考虑我们能够达到的最大的价值，即我们可以通过计算只放入一部分的k物品来计算最大的价值。我们要确保当前选择的路径的最大的价值要大于我们已经选择的路径的价值。这就是该问题的限界条件。通过该条件，可以减去很多的枝条，大大节省运行时间。

4. 算0-1背包问题程序代码 1. #include

2. #include 3. #include 4. #include 5.

6. 7. 8. 9.

int * pValue = NULL; //物品的价值 int * pWeight = NULL;//物品的重量 int counts = 0; //物品的个数

10. int *realSolution = NULL; //存放最终的解 11. int *testSolution = NULL; //存放每次走得路径所得的解 12.

13. /*计算在前k-1件物品已经做出决策的前提下，考虑可能达到的最大的效益值，返回一个上界， 14. 其中，cp代表背包中当前的价值，cw代表当前的重量，k代表是考虑第几个物品，m代表背包的最大容量 15. */

16. float BoundFound(int cp, int cw, int k, int m) 17. {

18. int i = k; 19. int c = cw;

20. float b = (float)cp; 21. while (i<=counts)

22. {

23. c += pWeight[i]; 24. if (c26. b += pValue[i]; 27. } 28. else 29. {

30. return (b+(1-(float)(c-m)/pWeight[i])*(pValue[i])); 31. } 32. i++; 33. }

34. return b; 35. } 36.

37. //m为背包的容量 38. void BackKnap(int m)

39. {

40. int currentWeight = 0; 41. int currentValue = 0; 42. int k = 1;

43. int finalValue = -1; 44. while(true) 45. {

46. while(k<=counts && (currentWeight + pWeight[k] <= m)) 47. {

48. testSolution[k] = 1;

49. currentWeight += pWeight[k]; 50. currentValue += pValue[k]; 51. k++; 52. }

53. if (k>counts) . {

55. finalValue = currentValue; 56. k = counts;

57. memmove((void *)realSolution, (void *)testSolution, (counts+1) * sizeof(int));

58. } 59. else 60. {

61. testSolution[k] = 0; 62. }

63. //如果发现这样的一条路径走得最好结果也没有我现在的结果好，则果断要求回溯 . while (BoundFound(currentValue, currentWeight, k+1, m) <= finalValue) 65. {

66. while((testSolution[k] != 1) && (k != 0)) k--;

67. if (k==0) 68. {

69. return ; 70. }

71. testSolution[k] = 0;

72. currentWeight -= pWeight[k]; 73. currentValue -= pValue[k]; 74. } 75. k++; 76. } 77. } 78.

79. void main() 80. {

81. printf(\"please input the counts of packages:\");

82. scanf(\"%d\", &counts);

83. printf(\"please input the volumn of the bag:\");

84. int m = 0;

85. scanf(\"%d\", &m);

86. pWeight = (int *)malloc((counts+1) * sizeof(int));

87. memset((void*)pWeight, 0, sizeof(int)* (counts+1));

88. for(int i = 1; i <= counts; i++) . {

90. printf(\"please input the weight of the %dth package:\", i);

91. scanf(\"%d\", pWeight + i); 92. }

93. pValue = (int *)malloc((counts+1) * sizeof(int));

94. memset((void*)pValue, 0, sizeof(int) * (counts+1));

95. for(i = 1; i <= counts; i++) 96. {

97. printf(\"please input the value of the %dth package:\", i);

98. scanf(\"%d\", pValue + i); 99. }

100. realSolution = (int *)malloc((counts+1

) * sizeof(int));

101. memset((void*)realSolution, 0, sizeof(int) * (counts+1));

102. testSolution = (int *)malloc((counts+1) * sizeof(int));

103. memset((void*)testSolution, 0, sizeof(int) * (counts+1)); 104. BackKnap(m);

105. printf(\"the best reslut is choosing \"); 106. int maximunValue = 0;

107. for (i = 1; i<=counts; i++) 108. {

109. if (realSolution[i] == 1) 110. {

111. maximunValue += pValue[i]; 112. printf(\"the %dth package \", i);

113. } 114. }

115. printf(\"\\n and the maximun value is %d\\n\",maximunValue); 116. }

5. 时间复杂性分析 算法复杂度分析：

从m(i，j)的递归式容易看出，算法需要O(nc)计算时间。当背包容量c很大时，算法需要的计算时间较多。例如，当c>2n时，算法需要Ω(n2n)计算时间。

实验结果 通过结果可以看出，利用回溯法成功的解出了0-1背包问题的最优解。