二维背包问题

 一 问题描述：

  二维费用的背包问题是指：
  对于每件物品，具有两种不同的费用；
  选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。
  问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，
  第i件物品所需的两种代价分别为a[i]和b[i]。两种代价可付出的最大值（两种背包容量）分别为V和U。物品的价值为w[i]。

  f[i][u][v] = max(f[i-1][u][v] , w[i] + f[i-1][u-a[i]][v-b[i]])
  二 加深
  同样的解决二维费用背包的只需要增加一维数组即可，即建立f[u][v]数组
  当为完全背包时候，uv正序，当为01背包的时候uv倒序。 
  当存在多重背包问题的时候，就需要将多重背包转换为01背包的情况。

 三 源代码分析

#include <iostream>
 using namespace std ; 
 const  int V = 1000 ;  //总成本b 
 const  int U = 1000 ;  //总成本a 
 const  int T = 5 ;    //物品的种类 
 
 int f[U+1][V+1] ;                                    //可以不装满 
 int w[T] = {8 , 10 , 4 , 5 , 5};                      //价值 
 int a[T] = {600 , 400 , 200 , 200 , 300};             //每一个的体积 
 int b[T] = {800 , 400 , 200 , 200 , 300};
 const int INF = -66536  ;
   
 int package()
 {
    for(int i = 1 ; i <= U ;i++) //条件编译，表示背包可以不存储满
      for(int j = 1 ; j <= V ;j++)
      f[i][j] = INF ;    
      
      f[0][0] = 0 ; //01
    
    for(int i = 0 ; i < T ; i++)
    {
      for(int u = U ; u >= a[i] ;u--) //必须全部从V递减到0
         {         
           for(int v = V ; v >= b[i] ;v--)                           
              f[u][v] = max(f[u-a[i]][v-b[i]] + w[i] , f[u][v])  ; //此f[v]实质上是表示的是i-1次之前的值。
         }                 
    }
    return f[U][V] ;        
 }
 
 int main()
 {
      
   int temp = package() ;   
   cout<<temp<<endl     ;   
   system("pause")      ;
   return 0 ;    
 }