算法设计与分析实验报告01背包问题

算法设计分析实验报告

课程名称：计算机算法设计分析 专 业： 班 级： 学 号： 姓 名：

指导教师：

一、问题的提出

问题描述：

给定n种物品和一个背包。物品i的重量是wi，体积是bi，其价值为vi，背包的容量为c，容积为d。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大?

在选择装入背包的物品时，对每种物品只有两个选择：即装入或不装入。不能重复装入，也不能只装入部分的物品i。 要求：

试设计一个解决此问题的动态规划算法，并分析算法的计算复杂性。

二、算法的基本思想

该问题具有最优子结构特征。标准0-1背包问题，MaxV表示前i个物品装入容量为j的背包中时所能产生的最大价值，结构体objec表示每一个可装入物品，其中w表示物品的重量，v表示物品的价值。如果某物品超过了背包的容量，则该物品一定不能放入背包，问题就变成了剩余i-1个物品装入容量为j的背包中所能产生的最大价值；如果该物品能装入背包，问题就变成i-1个物品装入容量为j-objec[i].w的背包所能产生的最大价值加上物品i的价值objec[i].v。

三、算法的程序实现

#include using namespace std;

int V [200][200][200];

int max(int a,int b) { if(a>=b) return a; else return b; }

int KnapSack(int n,int w[],int z[],int v[],int x[],int c,int b) {

int i,p,q;

for(i=0;i<=n;i++) V[i][0][0]=0;

for(p=0;p<=c;p++) for (q=0;q<=b;q++) V[0][p][q]=0;

for(i=0;i<=n-1;i++) for(p=0;p<=c;p++) for(q=0;q<=b;q++) if(p

V[i][p][q]=V[i-1][p][q]; else

V[i][p][q]=max(V[i-1][p][q],V[i-1][p-w[i]][q-z[i]]+v[i]); p=c; q=b;

for(i=n-1;i>=0;i--) { if(V[i][p][q]>V[i-1][p][q]) { x[i]=1; p=p-w[i]; q=q-z[i]; } else x[i]=0; }

cout<<\选中的物品是:\

for(i=0;i

cout<

int r=0;

for(i=0;i

return r; }

void main() { int mv; int w[150]; int z[150]; int v[150]; int x[150]; int n,i; int c; int b;//背包最大容量和容积 cout<<\请输入背包的最大容量:\ cin>>c; cout<<\请输入背包的最大容积:\ cin>>b; cout<<\输入物品数:\ cin>>n; cout<<\请分别输入物品的重量:\ for(i=0;i>w[i]; cout<<\请分别输入物品的体积:\