完全背包問(wèn)題：
一問(wèn)題描述：
有N種物品和一個(gè)容量為V的背包，每種物品都有無(wú)限件可用。
第i種物品的費(fèi)用是c[i]，價(jià)值是w[i]。
求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過(guò)背包容量，且價(jià)值總和最大。
二問(wèn)題實(shí)質(zhì)：
(1)與 01 背包不同，每個(gè)物品有多個(gè)，每種物品可以選擇k個(gè)。
且必須有 c[i] * k <= v 。
解決方法：
一
(1) 將完全背包轉(zhuǎn)化為01背包問(wèn)題，即第i種物品可以變成k個(gè)物品，且c[i] * k <= v 。
(2) 然后對(duì)問(wèn)題用01背包的算法進(jìn)行解決。
二
利用如下偽代碼：
for(int i = 0 ; i < T ; i++)
for(int v = c[i] ;v <= V ;v++)
f[v] = max(f[v] , f[v - c[i]] + w[i]) ;
此處問(wèn)題發(fā)現(xiàn) 與01背包問(wèn)題，只有在v的循環(huán)方向上不同，原因是
01背包必須保證，每個(gè)物品只選擇一次，而第i個(gè)物品選擇的必然是
第i-1次的物品，而不允許含有第i次得選擇。
完全背包則保證，每個(gè)物品均可以選擇多個(gè)。
所以第i個(gè)物品選擇時(shí)，可以包含本次的各個(gè)重量的選擇。
三代碼如下：
#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] = {500 , 600 , 400 , 400 , 400}; //每一個(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 = c[i] ; v <= V ;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 ;
}