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

《算法设计与分析实验报告—01背包问题.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计与分析实验报告—0/1背包问题-【问题描述】给定n种物品和一个背包。物品i的重量是，其价值为，背包容量为C。问应该如何选择装入背包的物品，使得装入背包中物品的总价值最大？【问题分析】0/1背包问题的可形式化描述为：给定C>0,>0,>0,，要求找出n元0/1向量，使得，而且达到最大。因此0/1背包问题是一个特殊的整数规划问题。【算法设计】设0/1背包问题的最优值为m(i,j)，即背包容量是j，可选择物品为i,i+1,…,n时0/1背包问题的最优值。由0/1背包问题的最优子结构性质，可以建立计算m(i,j)的递归式如下：ma

2、x{m(i+1,j),m(i+1,j-)+}m(i,j)=m(i+1,j)m(n,j)=0【算法实现】#include#include#includeintmin(intw,intc){inttemp;if(wc)temp=w;elsetemp=c;returntemp;}voidknapsack(intv[],intw[],int**m,

3、intc,intn)//求最优值{intjmax=min(w[n]-1,c);for(intj=0;j<=jmax;j++)m[n][j]=0;for(intjj=w[n];jj<=c;jj++)m[n][jj]=v[n];for(inti=n-1;i>1;i--)//递归部分{jmax=min(w[i]-1,c);for(intj=0;j<=jmax;j++)m[i][j]=m[i+1][j];for(intjj=w[i];jj<=c;jj++)m[i][jj]=max(m[i+1][jj],m[i+1][jj-w[i]]+v[

4、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]);cout<

5、解如下:"<

6、数:";cin>>n;cout<>c;int*v=newint[n+1];cout<>v[i];int*w=newint[n+1];cout<>w[j];int*x=newint[n+1];m=newint*[n+1];//动态的分配二维数组for(intp=0

7、;p