算法实验报告01背包问题

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

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

2、[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])V[i][j]=V[i-1][j];elseV[i][j]=V[i-1][j-w[i]]+v[i];}}}//以上构造动态规划表j=C;for(i=n;i>0

3、;i--){if(V[i][j]>V[i-1][j]){x[i]=1;j=j-w[i];}elsex[i]=0;}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]);printf("背包取得最大值：");printf("%4d",V[n][C]);}三、实验结果：四、实验分析：这次

4、实验用到的是动态规划法，0/1背包问题用动态规划法首先要构造动态规划表，用三个for语句实现；根据动态规划表每行的最大值变化确定每个元素的装入与否，逐步确定出装入背包的物品，背包容量的最大值也就是动态规划表最右下角。在本次实验中遇到了动态规划表构造紊乱的状况，经核查是因数组的初始位置0混淆成1造成的。"0-1"背包问题的贪心算法一、实验目的与要求：熟悉C/C++语言的集成开发环境；通过本实验加深对贪心算法、动态规划和回溯算法的理解。二、实验内容：掌握贪心算法、动态规划和回溯算法的概念和基本思想，分析并掌握"0-1"背包问题的三种算

5、法，并分析其优缺点。三、实验程序：#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,wx,k,ii;intV=0;//总价值初始化//计算单位价值printf("单位价值为：");for(m=0;m<5;m++){q[m]=m;x[m]=v[m]/w[m

6、];printf("x[%d]=%dt",m,x[m]);}//冒泡排序for(i=0;i<4;i++){for(j=0;j<4-i;j++){if(x[j]

7、or(i=0;i<5;i++)printf("x[%d]=%dt",i,x[i]);//装入背包for(i=0;i

8、验结果：二、实验分析：本次实验是以贪心算法解决背包问题，贪心算法要求出每个物品的单位价值，根据单位价值降序排列，再依次装入背包。当最后一个物品不能完全装入时，装入部分使背包容量为0。在本次实验中，遇到几个难题：1．保证物品按单位价值排列后依然能知道