频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
旅游背包(多维有界的背包问题)
2013-11-19 08:50:20      个评论      
收藏   我要投稿
描述:

想去旅游吗?那得先准备背包!

 

背包用来装旅游物品,现在共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;  
}  

 

 

点击复制链接 与好友分享!回本站首页
相关TAG标签 多维 背包 问题
上一篇:(字符串的模式匹配4.7.19——前缀数组suffix的应用)POJ 2752 Seek the Name, Seek the Fame(求解一个字符串中前缀和后缀一样的位
下一篇:华为面试题解析 - 01
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站