01背包(动态规划).docVIP

算法分析与设计实验报告 第 3 次实验 姓名 学号 班级 时间 11.14下午 地点 四合院 实验名称 动态规划法求解背包问题 实验目的 通过上机实验，要求掌握动态规划算法的问题描述、算法设计思想、程序设计。 利用动态规划算法求解背包问题，并计算出程序运行所需要的时间。 实验原理 给定几组数据，利用动态规划算法的思想，把 0-1 背包装满并使得其价值最大。 实验步骤 把问题分解成若干个子问题， 如背包仅可以容纳 1 个物品且可以容纳 的质量为一等。 依次求出各个子问题的最优解。 每个子问题的最优解又可以从它的子问题的最优解中得到。 通过各个子问题的最优解得到原问题的最优解。 关键代码 void KnapSack(int n,int w[],int v[],int x[],int C) { int i,j; int jMax=min(w[n]-1,C); for(j=0;j=jMax;j++) mV[n][j]=0; for(j=w[n];j=C;j++) mV[n][j]=v[n]; for(i=n-1;i1;i--) { jMax=min(w[n]-1,C); for(j=0;j=jMax;j++) mV[i][j]=mV[i+1][j]; for(j=w[i];j=C;j++) mV[i][j]=max(mV[i+1][j],mV[i+1][j-w[i]]+v[i]); } mV[1][C]=mV[2][C]; if(C=w[1]) mV[i][j]=max(mV[1][C],mV[2][C-w[1]]+v[1]); } void Traceback(int w[],int C,int n,int x[]){ for(int i=1;in;i++) if(mV[i][C]==mV[i+1][C]) x[i]=0; else { x[i]=1; C-=w[i]; } x[n]=(mV[n][C])?1:0; } 测试结果 实验心得 通过这次实验，我回顾了动态算法求解背包问题，在其中加入了舍伍德随机化取值过程，使数据分布更加均匀，让我熟悉了随机化算法，也让结果更加公平可靠。 本次实验在书本有详细的算法，但是刚开始的时候难以理解其精髓，后来通过和同学讨论才知道该算法与一般的做法有点不同，是从最后一个物品进行考虑的，这样方便了子问题的划分和代码的实现。这次实验让我知道，有时候不能墨守陈规，编写代码应该要打开自己的思路，从多方面进行考虑，才能写出最简单，方便的算法。 实验得分 助教签名 附录：完整代码 #includestdio.h #includestdlib.h #includetime.h int mV[200][200]; //前i个物品装入容量为j的背包中获得的最大价值 int max(int a,int b) { if(a=b) return a; else return b; } int min(int a,int b) { if(ab) return a; else return b; } void KnapSack(int n,int w[],int v[],int x[],int C) { int i,j; int jMax=min(w[n]-1,C); for(j=0;j=jMax;j++) mV[n][j]=0; for(j=w[n];j=C;j++) mV[n][j]=v[n]; for(i=n-1;i1;i--) { jMax=min(w[n]-1,C); for(j=0;j=jMax;j++) mV[i][j]=mV[i+1][j]; for(j=w[i];j=C;j++) mV[i][j]=max(mV[i+1][j],mV[i+1][j-w[i]]+v[i]); } mV[1][C]=mV[2][C]; if(C=w[1]) mV[i][j]=max(mV