01背包問(wèn)題

題目描述: ( 轉(zhuǎn)自背包九講1 )

有N件物品和一個(gè)容量為V的背包。第i件物品的費(fèi)用是c[i],，價(jià)值是w[i]。求解將哪些物品裝入背包可使價(jià)值總和最大,。

基本思路
這是最基礎(chǔ)的背包問(wèn)題,，特點(diǎn)是：每種物品僅有一件，可以選擇放或不放,。

用子問(wèn)題定義狀態(tài)：即f[i][v]表示前i件物品恰放入一個(gè)容量為v的背包可以獲得的最大價(jià)值,。則其狀態(tài)轉(zhuǎn)移方程便是：

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

這個(gè)方程非常重要，基本上所有跟背包相關(guān)的問(wèn)題的方程都是由它衍生出來(lái)的,。所以有必要將它詳細(xì)解釋一下：“將前i件物品放入容量為v的背包中”這個(gè)子問(wèn)題,，若只考慮第i件物品的策略（放或不放），那么就可以轉(zhuǎn)化為一個(gè)只牽扯前i-1件物品的問(wèn)題,。如果不放第i件物品,，那么問(wèn)題就轉(zhuǎn)化為“前i-1件物品放入容量為v的背包中”，價(jià)值為f[i-1][v],；如果放第i件物品,，那么問(wèn)題就轉(zhuǎn)化為“前i-1件物品放入剩下的容量為v-c[i]的背包中”，此時(shí)能獲得的最大價(jià)值就是f[i-1][v-c[i]]再加上通過(guò)放入第i件物品獲得的價(jià)值w[i],。

我的理解:

狀態(tài)轉(zhuǎn)移方程很好理解,我們想你的包是固定大小的,而一堆東西在外面,我們可以選擇放當(dāng)前拿到手的物品,那包的體積肯定要減小,如果我們不放這個(gè)物品,那背包里的物品價(jià)值和容量當(dāng)然保持不變了.

我喜歡設(shè)狀態(tài)數(shù)組為DP[i][v];

那么下標(biāo)分別是什么意思呢? 我們可以將 i 當(dāng)成物品的編號(hào),把v當(dāng)成當(dāng)前背包的體積

PKU ACM 有道原題鏈接:http://acm.pku.edu.cn/JudgeOnline/problem?id=3624

題目大意:

給定一個(gè)背包的物品數(shù)量和背包體積,然后分別輸入每個(gè)物品的體積和價(jià)值
最后輸出背包裝滿后最大價(jià)值量

樣例輸入:
4 6
1 4
2 6
3 12
2 7
樣例輸出:
23

我們輸出DP數(shù)組看一下:
  1  2  3  4  5  6
1 4  4  4  4  4  4
2 4  6  10 10 10 10
3 4  6  12 16 18 22
4 4  7  12 16 19 23

最上一排和最左一排是行下標(biāo)和列下標(biāo),我們看到 DP[1][1] 代表什么呢? 代表有第1個(gè)物品,并且當(dāng)前背包體積為1的時(shí)候最大的量,當(dāng)然是4了,而DP[2][2]呢? 代表當(dāng)前放入物品2,因?yàn)楫?dāng)前體積為2,而物品2體積就是2了,所以1就不能放了,好,DP[2][2] = 6,同理,DP[4][6] 就代表體積裝滿的時(shí)候,背包里面的總價(jià)值,為23.

這里時(shí)間復(fù)雜度不能優(yōu)化了,而我們可以優(yōu)化空間復(fù)雜度,我們觀察DP數(shù)組的最后一行:
先考慮上面講的基本思路如何實(shí)現(xiàn),，肯定是有一個(gè)主循環(huán)i=1..N，每次算出來(lái)二維數(shù)組f[i][0..V]的所有值,。那么,，如果只用一個(gè)數(shù)組f [0..V]，能不能保證第i次循環(huán)結(jié)束后f[v]中表示的就是我們定義的狀態(tài)f[i][v]呢,？f[i][v]是由f[i-1][v]和f[i-1] [v-c[i]]兩個(gè)子問(wèn)題遞推而來(lái),，能否保證在推f[i][v]時(shí)（也即在第i次主循環(huán)中推f[v]時(shí)）能夠得到f[i-1][v]和f[i-1][v -c[i]]的值呢？事實(shí)上,，這要求在每次主循環(huán)中我們以v=V..0的順序推f[v],，這樣才能保證推f[v]時(shí)f[v-c[i]]保存的是狀態(tài)f[i -1][v-c[i]]的值。偽代碼如下：
for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相當(dāng)于我們的轉(zhuǎn)移方程f[i][v]=max{f[i-1][v],f[i- 1][v-c[i]]}，因?yàn)楝F(xiàn)在的f[v-c[i]]就相當(dāng)于原來(lái)的f[i-1][v-c[i]],。如果將v的循環(huán)順序從上面的逆序改成順序的話,，那么則成了f[i][v]由f[i][v-c[i]]推知，與本題意不符,，但它卻是另一個(gè)重要的背包問(wèn)題P02最簡(jiǎn)捷的解決方案,，故學(xué)習(xí)只用一維數(shù)組解01背包問(wèn)題是十分必要的。
核心程序:
for ( int i = 1; i <= N; i++ )
{
 for ( int v = V; v>=1; --v )
 {
  if ( v >= cost[i] )
  {
   if ( DP[v-cost[i]] + value[i] >= DP[v] ) {
                         DP[v] = DP[v-cost[i]] + value[i];      
              }
}
 //DP[v-cost[i]]+value[i]就是說(shuō)目前包里要裝第i個(gè)物品
//看看裝第i個(gè)物品和不裝它哪個(gè)大,第一次開始時(shí)DP[6],就是說(shuō)可以裝
//單位重量的物品,然后依次類推,5,4,3,2,1,看看有或沒(méi)有第i個(gè)物品的總價(jià)值

C++ 代碼:

#include <iostream>
#include <vector>
using namespace std;

int main ()
{
 vector<int> value;
 vector<int> volume;
 vector<int> DP;
 int N,V;
 while ( cin >> N >> V )
 {
  value.resize(N+1);
  volume.resize(V+1);
  DP.clear();
  DP.resize(V+1);
  for ( int i = 1; i <= N; i++ )
  {
   cin >> volume[i] >> value[i];
  }
  for ( int i = 1; i <= N; i++ )
  {
   for ( int v = V; v >= 1; v-- )
   {
    if ( v >= volume[i] )
    {
     if ( DP[v-volume[i]] + value[i] >= DP[v] )
     {
      DP[v] = DP[v-volume[i]] + value[i];
     }
    }
   }
  }
  cout << DP[V] << endl;
 }
 return 0;
}