实验-2-用动态规划实现0-1背包问题.docx

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

1、实验二用动态规划实现0-1背包问题一．实验目的1.熟悉动态规划法的基本原理。2.通过本次实验加深对动态规划的理解。  二．实验内容及要求内容：.给定n种物品和一个背包。物品i的重量是w，其价值为v，背包容量为c。问应该如何选择装入背包的物品，使得装入背包中物品的总价值最大?要求：使用动态规划算法编程，求解0-1背包问题三．程序列表（1）#includeusingnamespacestd;intoptp[100][100];voidKnapsack(intm,intn,intw[10],intp[10])//n位物品数,m为背包的承受重量{f

2、or(inti=0;i<=m;i++){optp[0][i]=0;}for(intk=1;k<=n;k++){optp[k][0]=0;for(intj=1;j<=m;j++){if(w[k]<=j){if(p[k]+optp[k-1][j-w[k]]>optp[k-1][j])optp[k][j]=p[k]+optp[k-1][j-w[k]];elseoptp[k][j]=optp[k-1][j];}elseoptp[k][j]=optp[k-1][j];}}}voidTraceback(intm,intn,intw[10],intx[10]){intsum

3、=0;for(intk=n;k>=1;k--){if(optp[k][m]==optp[k-1][m])x[k]=0;else{x[k]=1;m=m-w[k];sum=sum+w[k];}}x[1]=optp[1][m]?1:0;cout<<"最大总重量:"<>n;cout<<"输入背包的总容量:";cin>>m;cout<<"依次输入物品的重量:"<>w

4、[i];}cout<<"依次输入物品的价值:"<>p[k];}Knapsack(m,n,w,p);Traceback(m,n,w,x);cout<<"最优解为:"<