二維背包問題
一 問題描述：
二維費(fèi)用的背包問題是指：
對于每件物品，具有兩種不同的費(fèi)用；
選擇這件物品必須同時付出這兩種代價；對于每種代價都有一個可付出的最大值（背包容量）。
問怎樣選擇物品可以得到最大的價值。設(shè)這兩種代價分別為代價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èi)用背包的只需要增加一維數(shù)組即可，即建立f[u][v]數(shù)組
當(dāng)為完全背包時候，uv正序，當(dāng)為01背包的時候uv倒序。
當(dāng)存在多重背包問題的時候，就需要將多重背包轉(zhuǎn)換為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]實質(zhì)上是表示的是i-1次之前的值。
}
}
return f[U][V] ;
}
int main()
{
int temp = package() ;
cout<<temp<<endl ;
system("pause") ;
return 0 ;
}