算法分析与设计实验报告第3次实验
姓名时间
杨玉茹331下午
学号地点
班级201508010325软件大楼330
计科1503
实验名称动态规划法求解背包问题
实验目的通过上机实验，要求掌握动态规划算法的问题描述、算法设计思想、程序设计。
实验原理
使用动态规划算法的原理，即将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。分析出背包问题的动态规划方程式，然后实现相应的代码，然后再进行再输入多组值进行验证，看输出结果，然后来验证自己的程序是否正确。
实验步骤
①首先求出最优子结构，设（y1y2y
）是所给01背包问题的一个最优解；②如果第i个物品的重量大于背包的容量，则装人前i个物品得到的最大价值和装入前i1个物品得到的最大价是相同的，即物品i不能装入背包，得出方程为：
Vi0V0j0③如果第i个物品的重量小于背包的容量，则会有一下两种情况：a如果把第i个物品装入背包，则背包物品的价值等于第i1个物品装入容量位jwi的背包中的价值加上第i个物品的价值vib如果第i个物品没有装入背包，则背包中物品价值就等于把前i1个物品装入容量为j的背包中所取得的价值。显然，取二者中价值最大的作为把前i个物品装入容量为j的背包中的最优解：
VijVi1jjwiVijmaxVi1jVi1jwivijwi④输入相应的测试值，进行判断程序的正确性；
关键代码
i
tK
api
t
i
twi
tvi
txi
tC
i
tijfori0i
i
Vi00forj0jCj
V0j0fori0i
1i
forj0jCj
fifjwiVijVi1j
elseVijmaxVi1jVi1jwivi
jCfori
1i0i
ifVijVi1jxi1jjwielsexi0pri
tf