二维背包问题
一 问题描述：
二维费用的背包问题是指：
对于每件物品，具有两种不同的费用；
选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。
问怎样选择物品可以得到最大的价值。设这两种代价分别为代价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 ;
}