用动态规划解0-1背包问题.docx

《用动态规划解0-1背包问题.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验一用动态规划解0-1背包问题一、实验目的与要求1、掌握动态规划算法求解问题的一般特征和步骤2、使用动态规划法编程求解0/1背包问题。二、实验内容0-1背包问题(knapsackproblem)：某商店有n个物品，第i个物品价值为vi，重量(或称权值)为wi，其中vi和wi为非负数,背包的容量为C，C为一非负数。目标是如何选择装入背包的物品使装入背包的物品总价值最大，所选商品的一个可行解即所选商品的序列如何。背包问题与0-1背包问题的不同点在于：在选择物品装入背包时，可以只选择物品的一部分，而不一定要选择物品的全部。三、问题描述给定n和物品和一

2、人背包，物品i的重量是wi，其价值为vi，问：如何选择装入背包的物品，使得装入背包的物品的总价值最大。举例:若商店一共有5类商品，重量分别为：34789，价值分别为：45101113，则所选商品的最大价值为24，所选商品的一个序列为00011。四、问题分析与算法设计动态规划原理：动态规划是一种将问题实例分解为更小的、相似的子问题并存储子问题的解而避免计算重复的子问题以解决最优化问题的算法策略。动态规划法所针对的问题有一个显著的特征，即它所对应的子问题树中的子问题呈现大量的重复。动态规划法的关键就在于：对于重复出现的子问题，只在第一次遇到时

3、加以求解，并把答案保存起来，让以后再遇到时直接引用而不必重新求解。五、实验结果源程序：#includeusingnamespacestd;voidknapsack(intm[30][30],intw[30],intv[30],intn,intC){for(inti=0;i<=C;i++)m[0][i]=0;for(inti=1;i<=n;i++){m[i][0]=0;for(intj=1;j<=C;j++){if(w[i]<=j){if(v[i]+m[i-1][j-w[i]]>m[i-1][j])m[i][j]=v[i]+m[i-1][

4、j-w[i]];elsem[i][j]=m[i-1][j];}elsem[i][j]=m[i-1][j];}}}voidtraceback(intm[30][30],intx[30],intw[30],intn,intC){for(intk=n;k>=2;k--){if(m[k][C]==m[k-1][C])x[k]=0;else{x[k]=1;C=C-w[k];}}x[1]=m[1][C]?1:0;}intmain(){intm[30][30],w[30],v[30],x[30],C,n;cout<<"请输入物品的总个数：";cin>>n;cout<<"

5、请输入背包的总容量：";cin>>C;cout<>w[i];}cout<>v[i];}knapsack(m,w,v,n,C);traceback(m,x,w,n,C);cout<<"最优解为："<

6、<