姓名:
学号:
班级:
"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(j<w[i])
V[i][j]=V[i-1][j];
else
{
if(V[i-1][j]>V[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 m,i,j,p,vx,wx,k,ii;
int V=0;//总价值初始化
//计算单位价值
printf("单位价值为:\n");
for(m=0;m<5;m++)
{
q[m]=m;
x[m]=v[m]/w[m];
printf("x[%d]=%d\t",m,x[m]);
}
//冒泡排序
for(i=0;i<4;i++)
{
for(j=0;j<4-i;j++)
{
if(x[j]<x[j+1])
{
//交换单位价值
p=x[j];
x[j]=x[j+1];
x[j+1]=p;
//交换价值对应位置
vx=v[j];
v[j]=v[j+1];
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("\n单位价值降序为:\n");
for(i=0;i<5;i++)
printf("x[%d]=%d\t",i,x[i]);
//装入背包
for(i=0;i<n&&w[i]<C;i++)
{
if(w[i]<=C)
{
V+=v[i];
C=C-w[i];
}
}
k=i;
if(C!=0)
{
V+=v[i]*C/w[i];
C=0;
}
for(ii=0;ii<=k;ii++)
{
printf("\n放入第%d个物品:\n物品的重量为:%d\n物品的价值为:%d\n背包剩余容量为:%d\n",q[ii]+1,w[ii],v[ii],C);
}
printf("\n总价值为:%d\t",V);
}
四、 实验结果:
五、 实验分析:
本次实验是以贪心算法解决背包问题,贪心算法要求出每个物品的单位价值,根据单位价值降序排列,再依次装入背包。当最后一个物品不能完全装入时,装入部分使背包容量为0。
在本次实验中,遇到几个难题:
1. 保证物品按单位价值排列后依然能知道他的原始顺序位置,经过几番思考,决定设置一个数组来保存该物品的原始位置,在冒泡算法交换时同时交换物品编号;
2. 装入背包过程如何保证装入不完整物品,即背包剩余容量不能满足完全放入下一个物品。
通过本次试验又熟悉了冒泡算法的应用,以及多重for循环的应用。
"0-1"背包问题的回溯算法
一、实验目的与要求:
熟悉C/C++语言的集成开发环境;
通过本实验加深对贪心算法、动态规划和回溯算法的理解。
二、 实验内容:
掌握贪心算法、动态规划和回溯算法的概念和基本思想,分析并掌握"0-1"背包问题的三种算法,并分析其优缺点。
三、实验程序:
#include <iostream.h>
//定义min、max函数
int min(int a,int b)
{
if(a>=b) return b;
else return a;
}
int max(int a,int b)
{
if(a>=b) return a;
else return b;
}
void Knapsack(int v[6],int w[6],int c,int n,int m[6][6])//
{
int jmax=min(w[n]-1,c);
for(int j=0;j<jmax;j++)
m[n][j]=0;
for(int p=w[n];p<=c;p++)
m[n][p]=v[n];
for(int i=n-1;i>1;i--)
{
jmax=min(w[i]-1,c);
for(int j=0;j<=jmax;j++)
m[i][j]=m[i+1][j];
for(int t=w[i];t<=c;t++)
m[i][t]=max(m[i+1][t],m[i+1][t-w[i]]+v[i]);
}
m[1][c]=m[2][c];
if(c>=w[1])
m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);
}
void Traceback(int m[6][6],int w[6],int c,int n,int x[6])
{
for(int i=1;i<n;i++)
if(m[i][c]==m[i+1][c]) x[i]=0;
else
{
x[i]=1;
c-=w[i];
}
x[n]=(m[n][c]!=0)?1:0;
}
void main()
{
int n1=5;
int c1=6;
int w1[6]={0,3,2,1,4,5};
int v1[6]={0,25,20,15,40,50};
int t[6][6];
int x1[6];
int m=0;
//cout<<"请输入背包的容量:"<<endl;
//cin>>c1;
cout<<"0-1背包如下:"<<endl;
cout<<"物品的重量分别为:"<<endl;
for(int p=1;p<6;p++)
cout<<w1[p]<<" ";
cout<<endl;
cout<<"物品的价值分别为:"<<endl;
for(int q=1;q<6;q++)
cout<<v1[q]<<" ";
cout<<endl;
cout<<"背包的容量为:"<<c1<<endl;
cout<<"要选择的物品是:"<<endl;
Knapsack(v1,w1,c1,n1,t);
//for(int i=1;i<=n1;i++)cout<<v1[i]<<endl;
Traceback(t,w1,c1,n1,x1);
for(i=1;i<=n1;i++)
if(x1[i]==1){
m+=v1[i];
cout<<"第"<<i<<"件物品"<<endl;}
cout<<"最大总价值为:"<<m<<endl;
}
四、实验结果:
五、实验分析:
本次实验用回溯法解决0/1背包问题,回溯法首先要建立0/1背包的解空间树,然后再回溯得出搜素空间,即解的范围,然后求出最佳答案。实验中先构造两个函数,Knapsack列出所有背包的解空间,Traceback对解空间进行搜索,得出答案。
第二篇:实验报告8 蛮力法与动态规划求解01背包问题
第八章《算法设计与分析》实验报告
班级: 学号: 姓名:
一、实验内容:
分别用蛮力法、动态规划法 求解0/1背包问题。
二、所用算法的基本思想及复杂度分析:
1、 蛮力法
1) 基本思想
2) 复杂度分析
2、 动态规划法
1) 基本思想
2) 复杂度分析
三、程序伪码:
四、源程序及注释:
五、运行输出结果:
六、调试和运行程序过程中产生的问题、采取的措施及获得的相关经验教训:
1