描述:
想去旅游吗?那得先准备背包!
背包用来装旅游物品,现在共n种(n<=50)旅游物品,每种物品都有体积vi,重量wi,数量ci,价值ti (vi,wi,ci和ti都为整数)。
限制体积最多V立方厘米(V<=1000),重量最多W公斤(W<=500)。
请问你如何选择物品,使得带上的物品总价值最大,这个最大总价值为多少?
比如:
物品 体积 重量 数量 价值
编号 (立方厘米) (公斤) (个) (元)
1 30 3 10 4
2 50 8 10 5
3 10 2 10 2
4 23 5 8 3
5 130 20 5 11
若V为500,W为100,则选择物品的最大价值为72(且72=10*4+10*2+4*3:由10件物品1,10件物品3,和4件物品4组成)。
这是一个多维且有界的背包问题,属于常规0-1背包问题的扩展问题。
输入格式:
第一行,物品的种类n,背包体积的限制V,背包载重量的限制W。n,V和W的范围如前所述。 接下来n行,每行为该种物品i的体积vi,重量wi,数量ci,价值ti (规定vi,wi,ci和ti都为整数)。输出格式:
仅一行,为选择物品子集所能获得的最大价值。输入样例:
5 500 100 30 3 10 4 50 8 10 5 10 2 10 2 23 5 8 3 130 20 5 11输出样例:
72
分析:
发现对于这个题目,很多同学使用直接的递归方式完成,这里使用动态规划的方法完成。
n种物品,每种物品体积v[i],重量w[i],c[i]件,价值t[i]。
设:m[i][x][y] 表示可选前i 种物品,所选物品总体积不超过x ,总重量不超过y ,的最大价值。
首先对三维数组初始化为0;
存在如下递归关系:
当 i=1 时:
m[1][x][y]=0 x<v[1]||y<w[1];
m[1][x][y]=min(x/v[1],y/[w[1],c[1])*t[1] x>=v[1]&&y>=w[1];
当 i>1 时:
m[i][x][y]=max{m[i-1][x][y],m[i-1][x-k*v[i]][y-k*w[i]]+k*t[i]} x>=v[i]&&y>=w[i]; 其中: 0<k<min(x/v[i],y/w[i],c[i]);m[i][x][y]=m[i-1][x][y] x<v[i]||y<w[i];
k表示背包能放入i物品最多的件数;
代码如下:
#include<iostream> using namespace std; int m[51][1001][501]={0}; //m[i][j][k] 表示可选前i 种物品,总体积不超过j, 总重量不超过k 的最大值 int v_arr[51]; //物品体积 int w_arr[51]; //重量 int c_arr[51]; //件数 int t_arr[51]; //价值 int min(int a,int b,int c){ //三个数找最小 int m; m=a; if(b<m) m=b; if(c<m) m=c; return m; } void func(int v,int w,int n){ //可选前n个物品,体积不超过v,重量不超过w int i=0,j=0; int x=0,y=0; int k=0,max=0; for(x=0;x<=v;x++) for(y=0;y<=w;y++) if((x/v_arr[1]>0)&&(y/w_arr[1]>0)) //x>=v_arr[1]&&y>=w_arr[1] m[1][x][y]=min(x/v_arr[1],y/w_arr[1],c_arr[1])*t_arr[1]; //m[1][x][y]取最大值 else m[1][x][y]=0; //x<v_arr[1]&&y<w_arr[1] for(i=2;i<=n;i++) //从第i=2开始填充 for(x=0;x<=v;x++) for(y=0;y<=w;y++){ max=m[i-1][x][y]; if((x>=v_arr[i])&&(y>=w_arr[i])){ for(k=0;k<=min(x/v_arr[i],y/w_arr[i],c_arr[i]);k++) if((m[i-1][x-k*v_arr[i]][y-k*w_arr[i]]+k*t_arr[i])>max) //找出符合的最大的 max=(m[i-1][x-k*v_arr[i]][y-k*w_arr[i]]+k*t_arr[i]); m[i][x][y]=max; } else m[i][x][y]=m[i-1][x][y]; } } int main(){ int n=0; //物品种类 int v=0; //背包体积 int w=0; //背包载重 cin>>n>>v>>w; for(int i=1;i<=n;i++) cin>>v_arr[i]>>w_arr[i]>>c_arr[i]>>t_arr[i]; func(v, w, n); cout<<m[n][v][w]; return 0; }