科技学院算法设计与分析实验报告

华北电力大学科技学院实验报告||实验名称 课程名称 ||专业班级学号指导教师学生姓名成绩实验日期实验一 用动态规划方法求解0-1背包问题一、 实验目的及要求1•理解动态规划算法的概念2. 掌握动态规划算法的基本要素：最优子结构性质和重叠子问题性质3. 掌握设计动态规划算法的步骤4•通过具体实例一一0-1背包问题学习动态规划算法设计策略二、 所采用存储结构数组存储结构三、 实验步骤1•问题：有n个物品{U1, U2, U3...Un}其体积和价值分别为Si和Vi,在限定背包的 情况下，选取物品使背包价值最大2•分析：不能放Si>C 能放max （价值）{放，不放} 最优子结构设{yl, y2, y3...yk}是最优子结构，则{y2...yk} —定是C-S1的最优解设w[i][j]表示从前i件物品中选择若干件放入到容量为j的背包中所获得的最大价值0 i 二 0或j 二 0w[i][j]{ w Li川 Si > jmax{Vi + w[i -1][ j - Si], w[i -1][ j]} Si < j0 < i < n0 < j < c例：C=9,S={2,3,4,5} V={3,4,5,7}012345678900000000000100333333332003447777730034578991240034578101112代码：//0-1背包问题#include #define N 100 int max(int a,int b) {return a>b?a:b;}main(){int c,s[N],v[N],n;printf("输入物品个数：\n"); scanf("%d", &n);printf("输入背包体积：\n"); scanf("%d", &c);printf("输入每个物品的体积：\n"); for(int a=0;a=s[i—l]) w[i][j]=max(w[i-l][j],v[iT]+w[iT][j-s[iT]]); elsew[i][j]=w[i-l][j]; if(i==n && j==c) printf("背包可容纳最大价值为：％d\n",w[i][j]);}}四、实验结果五、心得体会 通过0-1背包问题的求解，我了解了动态规划的方法，更熟悉的掌握了 C++ 中地址的分配和数据的存储，更能熟悉的应用数组的输入存储和调用，更清 晰的了解了二维数组的动态分配问题，知道了在程序中如何使用除main() 以外的其他方法，并调用联系在一起，总之通过本次0-1背包问题的求解我 掌握了更清晰的求解方法，并把之前的知识都回顾了，同时也提升了自己 的动手能力和汇编能力，总而言之知这次实验我的收获很大。

实验二 用贪心算法求解部分背包问题一、 实验目的及要求1•理解贪心算法算法的概念2.掌握贪心算法的基本要素：最优子结构性质和贪心选择性质3•掌握设计贪心算法的步骤4•通过具体实例一一部分背包问题学习贪心算法设计策略二、 所采用存储结构数组存储结构三、 实验步骤1•问题：有n个物品{U1, U2, U3...Un}其体积和价值分别为Si和Vi,在限定背包的 情况下，选取物品使背包价值最大max 工 Vi x Xi2•分析：目标函数： i=i x E [0，1]工 Si x Xi < C约束条件：t贪心选择：选择单位价值最大的物品 最优子结构：设 w{W1, W2...Wk}是全局最优解，则 M={W1, W2...Wk-1, Wk}且 Sk'=Sk-S —定是 C-S 的最优解例：n=4，C=5, S={1，2，3，4}，V={4，3，2，1}代码： //部分背包问题#include#define N 100main() {int n;double r[N],x[N],c,s[N],v[N];printf("输入物品个数：\n");scanf("%d", &n);printf("输入背包体积：\n");scanf("%lf", &c);printf("输入每个物品的体积：\n");for(int a=0;a

难度在于要是排序后物品的编号就会发生改变，输出的就不是之前的编号的物品， 导致错误，后来发现如果为每一个物品保存一个副本，然后将它们的编号进行对比，就 可以进行正确的输出了感觉每一次实验都有学到东西，很开心。