算法实验报告01背包问题

《算法实验报告01背包问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、......河北工业大学计算机科学与软件学院算法分析与设计实验报告实验：0/1背包问题专业word可编辑.......姓名：学号：班级："0-1"背包问题的动态规划算法一、实验目的与要求：熟悉C/C++语言的集成开发环境；通过本实验加深对贪心算法、动态规划和回溯算法的理解。二、实验内容：掌握贪心算法、动态规划和回溯算法的概念和基本思想，分析并掌握"0-1"背包问题的三种算法，并分析其优缺点。三、实验程序：#include"stdio.h"intn=5;intw[]={0,3,2,1,4,5};专业word可编辑.......intv[]

2、={0,25,20,15,40,50};intx[5];intV[6][7];intC=6;voidmain(void){inti,j;for(i=0;i<=n;i++)V[i][0]=0;for(j=0;j<=C;j++)V[0][j]=0;for(i=1;i<=n;i++){for(j=1;j<=C;j++){if(jV[i-1][j-w[i]]+v[i])专业word可编辑.......V[i][j]=V[i-1][j];elseV[i][j]=V

3、[i-1][j-w[i]]+v[i];}}}//以上构造动态规划表j=C;for(i=n;i>0;i--){if(V[i][j]>V[i-1][j]){x[i]=1;j=j-w[i];}elsex[i]=0;}专业word可编辑.......printf("动态规划表如下：");for(i=0;i<6;i++){for(j=0;j<7;j++){printf("%8d",V[i][j]);}printf("");}printf("装入背包物品：");for(i=0;i<6;i++)printf("%4d",x[i]);pri

4、ntf("背包取得最大值：");printf("%4d",V[n][C]);}三、实验结果：专业word可编辑.......四、实验分析：这次实验用到的是动态规划法，0/1背包问题用动态规划法首先要构造动态规划表，用三个for语句实现；根据动态规划表每行的最大值变化确定每个元素的装入与否，逐步确定出装入背包的物品，背包容量的最大值也就是动态规划表最右下角。在本次实验中遇到了动态规划表构造紊乱的状况，经核查是因数组的初始位置0混淆成1造成的。专业word可编辑......."0-1"背包问题的贪心算法一、实验目的与要求：熟悉C

5、/C++语言的集成开发环境；通过本实验加深对贪心算法、动态规划和回溯算法的理解。二、实验内容：掌握贪心算法、动态规划和回溯算法的概念和基本思想，分析并掌握"0-1"背包问题的三种算法，并分析其优缺点。三、实验程序：#include"stdio.h"voidmain(void){intC=6;//背包容量6intn=5;//5个物品intw[]={3,2,1,4,5};//物品重量intv[]={25,20,15,40,50};//物品价值intx[]={0,0,0,0,0};//单位价值初始化intq[5];intm,i,j,p,vx,

6、wx,k,ii;intV=0;//总价值初始化//计算单位价值printf("单位价值为：");专业word可编辑.......for(m=0;m<5;m++){q[m]=m;x[m]=v[m]/w[m];printf("x[%d]=%dt",m,x[m]);}//冒泡排序for(i=0;i<4;i++){for(j=0;j<4-i;j++){if(x[j]

7、...v[j+1]=vx;//交换重量对应位置wx=w[j];w[j]=w[j+1];w[j+1]=wx;//交换商品编号m=q[j];q[j]=q[j+1];q[j+1]=m;}}}printf("单位价值降序为：");for(i=0;i<5;i++)printf("x[%d]=%dt",i,x[i]);//装入背包for(i=0;i

8、or(ii=0;ii<=k;ii++){printf("放入第%d个物品：物品的重量为：%d物品的价值为：%d背包剩余容量为：%d",q[ii]+1,w[ii],v[ii],C);}pr