动态规划解决0-1背包问题实验及其代码

实验报告3动态规划实验3动态规划解决0-1背包问题一、实验目的1）掌握动态规划动态方程的递归原理和过程；2）利用动态规划方法解决0-1背包问题；二、实验内容动态规划解决0-1背包问题三、算法设计1）编写voidValue(Typep[],Typew[],Typec,Typen,Typef[nMax][nMax])函数，用以计算各个最优子序列的值；2）编写voidcompute(Typef[nMax][nMax],Typew[],Typep[],Typec,Typen,Typex[])函数用以确定计算装入的物品x[]和装入的物品的总重量totalWeight；3）编写主函数，控制输入输出；4）改进和检验程序。四、程序代码//动态规划算法解决-1背包问题的c++程序#include"stdafx.h"#include<iostream>#include<iomanip>usingnamespacestd;inttotalWeight=0;//物品的总重量constintnMax=100;template<classType>voidValue(Typep[],Typew[],Typec,Typen,Typef[nMax][nMax]){//计算value[i][j] //置初值条件 for(intj=0;j<=c;j++) if(j>=w[0]) f[0][j]=p[0]; else f[0][j]=0; //计算各问题的最优值 for(inti=1;i<n;i++){ for(intj=0;j<=c;j++) if(j>=w[i]&&f[i-1][j]<f[i-1][j-w[i]]+p[i]) f[i][j]=f[i-1][j-w[i]]+p[i]; else f[i][j]=f[i-1][j]; }}template<classType>voidcompute(Typef[nMax][nMax],Typew[],Typep[],Typec,Typen,Typex[]){ //计算x[]的值和装入的物品的总重量totalWeight； intc0=c,totalValue=0; for(inti=n-1;i>0;i--) if(f[i][c0]>f[i-1][c0]){ x[i]=1;c0=c0-w[i]; totalValue=totalValue+p[i]; totalWeight=totalWeight+w[i]; } else x[i]=0; if(f[n-1][c]>totalValue){ x[0]=1; totalWeight=totalWeight+w[0]; } else x[0]=0;}int_tmain(intargc,_TCHAR*argv[]){ inti,x[nMax],*weight,*price,volume,counts,value[nMax][nMax]; charname[nMax][30];//物品的名称 cout<<"请输入背包的容量"<<endl; cin>>volume;//背包的容量 cout<<"请输入待装物品的总个数"<<endl; cin>>counts;//物品的个数 weight=newint[counts];//物品重量 price=newint[counts];//物品的单价 cout<<"请输入各个物品的名称:重量:价值:"<<endl; for(i=0;i<counts;i++) cin>>name[i]>>weight[i]>>price[i]; Value(price,weight,volume,counts,value); compute(value,weight,price,volume,counts,x); cout<<"0-1背包问题（装入背包的物品重量，价值，名字以表格的形式表示如下：）"<<endl; cout<<setw(10)<<"i"<<setw(12)<<"wieght[i]"<<setw(12)<<"price[i]"<<setw(12)<<"name[i]"<<endl; for(i=0;i<counts;i++){ if(x[i]==1) cout<<setw(10)<<i<<setw(10)<<weight[i]<<setw(10)<<price[i]<<setw(10)<<name[i]<<endl; } cout<<"装如背包的总重量:"<<totalWeight<<"总价值为:"<<value[counts-1][volume]<<endl; dele