算法分析与设计实验报告——0-1背包问题的动态规划算法实现
目录： 算法分析与设计实验报告——0-1背包问题的动态规划算法实现一、 实验目的二、实验要求三、 实验原理四、 实验过程(步骤)五、 运行结果六、实验分析与讨论七、实验特色与心得附件一 实验过程(步骤)附件二 运行结果
一、 实验目的
掌握动态规划的基本思想和解决问题的基本步骤，认识动态规划和分治法的联系与区别，对比解决同一问题的两种算法设计策略的时间复杂性。
二、实验要求
用c++语言实现用动态规划算法解决0-1背包问题，分析时间复杂性，体会动态规划算法解决问题的基本思路和步骤。
三、 实验原理
0-1 背包问题具有最优子结构性质，可以据此定义递归关系，建立递归方程，并以自底向上的方式计算最优值，根据计算最优值时的得到的信息，构造最优解。
设所给 0-1 背包问题的子问题的最优值 m(i，j) ，即 m(i，j) 是背包重量为 j ，可选物品为 i，i+1，…，n-1 时的最优值。由最优子结构性质，可以计算出 m(i，j) 的递归式如下：
四、 实验过程(步骤)
见附件一
实验步骤、特点
重要源代码（流操作的部分要醒目的提示并注释）
五、 运行结果
见附件二
六、实验分析与讨论
刚开始运行并没有得到最优解，经过检查程序发现有一个判断条件出错了，修改后结果依然不变，再次阅读程序没有发现问题，然后开始查阅课本，再重新理解一下这个问题。思考后想到了数组的范围设置错误，导致了结果偏移的问题。修改后结果得到了最优解。
七、实验特色与心得
0-1 背包问题具有最优子结构性质，所以可以用动态规划方法求解。根据这种性质定义递归关系并建立递归方程，以自底向上的方式计算最优值。而且以后编程时要彻底理解问题后再构造算法。
附件一 实验过程(步骤) #include <bits/stdc++.h>#define maxn 100using namespace std;void Knapsack(int *v, int *w, int c, int n, int (*m)[maxn]) { //先判断第n个物品能不能装入背包 int jMax = min(w[n] – 1, c); //当0<=j<=wn时，m(n，j)=0 for (int j = 0; j <= jMax; j++) { m[n][j] = 0; } //当j>=wn时，m(n，j)=vn for (int j = w[n]; j <= c; j++) { m[n][j] = v[n]; } //再从n-1往前开始判断第n个物品到第i个物品能不能装下 for (int i = n – 1; i > 1; i–) { jMax = min(w[i] – 1, c); for (int j = 0; j < jMax; j++) { m[i][j] = m[i + 1][j]; } for (int j = w[i]; j <= c; j++) { m[i][j] = max(m[i + 1][j], m[i + 1][j – w[i]] + v[i]); } } //判断第n个到第1个物品能不能装下 m[1][c] = m[2][c]; if (c >= w[1]) m[1][c] = max(m[1][c], m[2][c – w[1]] + v[1]);}//回溯查找最优序列，能装下的赋值为1，不能装下的赋值为0void Traceback(int (*m)[maxn], int *w, int c, int n, int *x) { for (int i = 1; i < n; i++) { if (m[i][c] == m[i + 1][c]) x[i] = 0; else { x[i] = 1; c -= w[i]; } } x[n] = (m[n][c]) ? 1 : 0;}int main() { //进行数据输入 int n, c; cout << “请输入物品数量 n=”; cin >> n; cout << “请输入背包容量 c=”; cin >> c; int w[n]; cout << “请依次输入各物品的重量：”; for (int i = 1; i <= n; i++) { cin >> w[i]; } int v[n]; cout << “请依次输入各物品的价值：”; for (int i = 1; i <= n; i++) { cin >> v[i]; } int m[maxn][maxn]; int x[n]; int max_weight = 0; int max_value = 0; //进行查找与回溯 Knapsack(v, w, c, n, m); Traceback(m, w, c, n, x); //输出最优序列和最优重量与最优价值 cout << “最优装载序列为：\n”; for (int i = 1; i <= n; i++) { printf(“%d “, x[i]); max_weight += (x[i] * w[i]);美国高防vps max_value += (x[i] * v[i]); } cout << endl; printf(“最大重量为： %d\n最大价值为： %d\n”, max_weight, max_value); return 0;}/*5102 2 6 5 46 3 5 4 6*/ 附件二 运行结果
86433459
