01背包問題總結(jié)
一 問題描述：
有N件物品和一個(gè)容量為V的背包。第i件物品的費(fèi)用是c[i]，價(jià)值是w[i]。求解將哪些物品裝入背包可使價(jià)值總和最大。
所謂01背包，表示每一個(gè)物品只有一個(gè)，要么裝入，要么不裝入。
二 解決方案：
考慮使用dp問題 求解，定義一個(gè)遞歸式 opt[i][v] 表示前i個(gè)物品，在背包容量大小為v的情況下，最大的裝載量。
opt[i][v] = max(opt[i-1][v] , opt[i-1][v-c[i]] + w[i])
解釋如下：
opt[i-1][v] 表示第i件物品不裝入背包中，而opt[i-1][v-c[i]] + w[i] 表示第i件物品裝入背包中。
花費(fèi)如下：
時(shí)間復(fù)雜度為o(V * T) ，空間復(fù)雜度為o(V * T) 。 時(shí)間復(fù)雜度已經(jīng)無法優(yōu)化，但是空間復(fù)雜度則可以進(jìn)行優(yōu)化。
但必須將V 遞減的方式進(jìn)行遍歷，即V.......0 的方式進(jìn)行。
三 初始化：
（1）若要求背包必須放滿，則初始如下：
f[0] = 0 , f[1...V]表示-INF。表示當(dāng)容積為0時(shí)，只接受一個(gè)容積為0的物品入包。
（2）若要求背包可以空下，則初始化如下：
f[0...V] = 0 ，表示任意容積的背包都有一個(gè)有效解即為0。
具體解釋如下：
初始化的f數(shù)組事實(shí)上就是在沒有任何物品可以放入背包時(shí)的合法狀態(tài)。
如果要求背包恰好裝滿，那么此時(shí)只有容量為0的背包可能被價(jià)值為0的nothing“恰好裝滿”，
其它容量的背包均沒有合法的解，屬于未定義的狀態(tài)，它們的值就都應(yīng)該是-∞了。
如果背包并非必須被裝滿，那么任何容量的背包都有一個(gè)合法解“什么都不裝”，
這個(gè)解的價(jià)值為0，所以初始時(shí)狀態(tài)的值也就全部為0了。
四 代碼如下：
/**//*
01背包，使用了優(yōu)化后的存儲(chǔ)空間
建立數(shù)組
f[i][v] = max(f[i-1][v] , f[i-1][v-c[i]] + w[i])
將前i件物品，放入容量為v的背包中的最大值。
下面介紹一個(gè)優(yōu)化，使用一維數(shù)組，來表示
(1) f[v]表示每一種類型的物品，在容量為v的情況下，最大值。
但是體積循環(huán)的時(shí)候，需要從v----1循環(huán)遞減。
初始化問題：
(1)若要求背包中不允許有剩余空間，則可以將f[0]均初始化為0，其余的f[1
..n]均初始化為-INF 。
表示只有當(dāng)容積為0 的時(shí)候，允許放入質(zhì)量為0的物品。
而當(dāng)容積不為0的情況下，不允許放入質(zhì)量為0的物品，并且把狀態(tài)置為未知狀態(tài)。
(2)若要求背包中允許有剩余空間 ，則可以將f[1n]，均初始化為0。
這樣，當(dāng)放不下去的時(shí)候，可以空著。
*/
#include <iostream>
using namespace std ;
const int V = 1000 ; //總的體積
const int T = 5 ; //物品的種類
int f[V+1] ;
//#define EMPTY //可以不裝滿
int w[T] = {8 , 10 , 4 , 5 , 5}; //價(jià)值
int c[T] = {600 , 400 , 200 , 200 , 300}; //每一個(gè)的體積
const int INF = -66536 ;
int package()
{
#ifdef EMPTY
for(int i = 0 ; i <= V ;i++) //條件編譯，表示背包可以不存儲(chǔ)滿
f[i] = 0 ;
#else
f[0] = 0 ;
for(int i = 1 ; i <= V ;i++)//條件編譯，表示背包必須全部存儲(chǔ)滿
f[i] = INF ;
#endif
for(int i = 0 ; i < T ; i++)
{
for(int v = V ; v >= c[i] ;v--) //必須全部從V遞減到0
{
f[v] = max(f[v-c[i]] + w[i] , f[v]) ; //此f[v]實(shí)質(zhì)上是表示的是i-1次之前的值。
}
}
return f[V] ;
}
int main()
{
int temp = package() ;
cout<<temp<<endl ;
system("pause") ;
return 0 ;
}