河北工业大学计算机科学与软件学院 算法分析与设计实验报告 实验：0/1 背包问题 姓名： 学号： 班级： "0 -1 "背包问题的动态规划算法 一、 实验目的与要求： 熟悉 C /C ++语言的集成开发环境； 通过本实验加深对贪心算法、动态规划和回溯算法的理解。 二、 实验内容： 掌握贪心算法、动态规划和回溯算法的概念和基本思想，分析并掌握"0-1"背包问题的三种算法，并分析其优缺点。 三、 实验程序： #include"stdio.h" int n=5; int w[]={0,3,2,1,4,5}; int v[]={0,25,20,15,40,50}; int x[5]; int V[6][7]; int C=6; void main(void) { int i,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]; else V[i][j]=V[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]; } else x[i]=0; } printf("动态规划表如下：\n"); for(i=0;i<6;i++) { for(j=0;j<7;j++) { printf("%8d",V[i][j]); } printf("\n"); } printf("装入背包物品：\n"); for(i=0;i<6;i++) printf("%4d",x[i]); printf("\n 背包取得最大值：\n"); printf("%4d\n",V[n][C]); } 三、实验结果： 四、实验分析： 这次实验用到的是动态规划法，0/1 背包问题用动态规划法首先要构造动态规划表，用三个 for语句实现；根据动态规划表每行的最大值变化确定每个元素的装入与否，逐步确定出装入背包的物品，背包容量的最大值也就是动态规划表最右下角。在本次实验中遇到了动态规划表构造紊乱的状况，经核查是因数组的初始位置 0 混淆成 1 造成的。 "0 -1 "背包问题的贪心算法 一、 实验目的与要求： 熟悉 C /C ++语言的集成开发环境； 通过本实验加深对贪心算法、动态规划和回溯算法的理解。 二、 实验内容： 掌握贪心算法、动态规划和回溯算法的概念和基本思想，分析并掌握"0-1"背包问题的三种算法，并分析其优缺点。 三、 实验程序： #include"stdio.h" void main(void) { int C=6;//背包容量 6 int n=5;//5 个物品 int w[]={3,2,1,4,5};//物品重量 int v[]={25,20,15,40,50};//物品价值 int x[]={0,0,0,0,0};//单位价值初始化 int q[5]; int...
VIP
