指导教师对实验报告的评语
成绩：
指导教师签字：
年 月 日
10
实验三：0-1背包问题的动态规划算法设计
一、实验目的及要求
1.了解并掌握动态规划算法的设计思想。
2.利用动态规划算法的设计思想实现0-1背包问题的算法设计。
二、实验环境
使用C++语言；
在windows环境下使用CodeBlocks调试并运行。
三、实验内容
1.了解并掌握动态规划的设计思想。
2.利用动态规划算法的思想解决0-1背包问题。
四、算法描述及实验步骤
每种物品一件，可以选择放1或不放0。
用子问题定义状态：即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]。
五、调试过程及实验结果
11
六、总结
0-1背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想，另外，别的类型的背包问题往往也可以转换成0-1背包问题求解。通过这次实验我对动态规划算法的认识又有了新的提高。
12
指导教师对实验报告的评语
成绩：
指导教师签字：
年 月 日
13
实验四：背包问题的贪心算法
一、 实验目的：
运用贪心算法思想，设计解决上述问题的算法，找出最大背包价值的装法。 二、实验要求
1. 用c++语言实现背包问题的贪心算法。 2.掌握贪心思想的应用。 三、实验原理
在贪心算法中采用逐步构造最优解的办法，在每个阶段，都做出一个看上去最优的决策（在一定的标准下 ），决策一旦做出就不可更改。
四、实验过程(步骤) 1. 定义背包结构体： struct stone { int name;
int weight;//物品的剩余重量 int weight_t;//物品的重量 float benefit;//物品的价值 //float b; };
2. 定义函数void sort(stone *data,int num) //计算物品的单位重量的价值，并进行排序 3. 定义主函数并完成贪心选择。 4.分析算法复杂性分析：
该算法的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此，算法的计算时间上界为O（n*logn）。
与0-1背包问题类似，所不同的是在选择物品i装入背包时 ，可以选择物品i的一部分，可以选择物品i 可以选择物品 的一部分，而不一定要全部装入背包， 1≤i≤n。 这2类问题都具有最优子结构 ，最优子结构性质，极为相似，但 最优子结构 背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。
五、运行结果
14