精选优质文档-倾情为你奉上实验五：贪心算法求解背包问题实验内容应用贪心算法求解离散背包问题，分析时间复杂度。有一个承重为W的背包和n个物品，它们各自的重量和价值分别是wi和vi（1=i=n），设 求这些物品中最有价值的一个子集。如果每次选择某一个物品的时候，只能全部拿走，则这一问题称为离散（0-1）背包问题；如果每次可以拿走某一物品的任意一部分，则这一问题称为连续背包问题。 算法思想 动态规划的思想： 对较小的子问题进行一次求解，并把结果记录下来，然后利用较小问题的解，求解出较大问题的解，直到求解出最大问题的解。引进一个二维数组chMAXMAX，用chij记录CH1与CH2的LCS 的长度，bij记录chij是通过哪一个子问题的值求得的，以决定搜索的方向。我们是自底向上进行递推计算，那么在计算chi,j之前，chi-1j-1，chi-1j与chij-1均已计算出来。此时我们根据CH1 i = CH2j还是CH1i != CH2j，就可以计算
