2.1 題目
有 N 種物品和一個容量為 V 的背包,每種物品都有無限件可用。放入第 i 種物品
的費用是 C i ,價值是 W i 此再。求解:將哪些物品裝入背包,可使這些物品的耗費的費用總
和不超過背包容量,且價值總和最大。
2.2 基本思路
這個問題非常類似于 01 背包問題,所不同的是每種物品有無限件摘符。也就是從每種
物品的角度考慮,與它相關(guān)的策略已并非取或不取兩種,而是有取 0 件策吠、取 1 件、取 2
件......直至取 ?V /C i ? 件等許多種带族。
如果仍然按照解 01 背包時的思路,令 F [i, v] 表示前 i 種物品恰放入一個容量為 v
的背包的最大權(quán)值蟀给。仍然可以按照每種物品不同的策略寫出狀態(tài)轉(zhuǎn)移方程,像這樣:
F [i, v] = max{F [i ? 1, v ? kCi ] + kWi | 0 ≤ kCi ≤ v}
#include <cstdio>
#include<algorithm>
#include<string.h>
#define Max(a,b) a>b?a:b
using namespace std;
int main()
{
int t;
int dp[4][10010],val[4]={0,150,200,350},vom[4]={0,150,200,350};
scanf("%d",&t);
while(t--)
{
int v;
scanf("%d",&v);
memset(dp,0,sizeof(dp));
for(int i=1;i<=3;i++)
{
for(int j=0;j<=v;j++)//v必須升序
{
for(int k=v/vom[i];k>=0;k--)//k必須降序
{
if(j-k*vom[i]>=0)
dp[i][j]=Max(dp[i-1][j],dp[i][j-k*vom[i]]+k*val[i]);
else dp[i][j]=dp[i-1][j];
}
}
}
printf("%d\n",v-dp[3][v]);
}
}
這跟 01 背包問題一樣有 O(VN ) 個狀態(tài)需要求解,但求解每個狀態(tài)的時間已經(jīng)不
是常數(shù)了,求解狀態(tài) F [i, v] 的時間是 O( C Vi ) ,總的復(fù)雜度可以認(rèn)為是 O(NV ΣV/Ci ) ,是
比較大的。
將 01 背包問題的基本思路加以改進,得到了這樣一個清晰的方法择克。這說明 01 背包
問題的方程的確是很重要,可以推及其它類型的背包問題。但我們還是要試圖改進這個
復(fù)雜度壹堰。
2.4 轉(zhuǎn)化為 01 背包問題求解
01 背包問題是最基本的背包問題,我們可以考慮把完全背包問題轉(zhuǎn)化為 01 背包問
題來解骡湖。
最簡單的想法是,考慮到第 i 種物品最多選 ?V /Ci ? 件,于是可以把第 i 種物品轉(zhuǎn)
化為 ?V /Ci ? 件費用及價值均不變的物品,然后求解這個 01 背包問題。這樣的做法完
全沒有改進時間復(fù)雜度,但這種方法也指明了將完全背包問題轉(zhuǎn)化為 01 背包問題的思
路:將一種物品拆成多件只能選 0 件或 1 件的 01 背包中的物品谆焊。
更高效的轉(zhuǎn)化方法是:把第 i 種物品拆成費用為 Ci*2^k 换途、價值為 Wi*2^k 的若干件物
品,其中 k 取遍滿足 Ci*2^k ≤ V 的非負(fù)整數(shù)。
這是二進制的思想剃执。因為,不管最優(yōu)策略選幾件第 i 種物品,其件數(shù)寫成二進制后,
總可以表示成若干個 2^k 件物品的和懈息。這樣一來就把每種物品拆成 O(log ?V /Ci ?) 件物
品,是一個很大的改進。
2.5 O(V N ) 的算法
這個算法使用一維數(shù)組,先看偽代碼:
F [0..V ] ←0
for i ← 1 to N
for v ← C i to V
F [v] ← max(F [v], F [v ? Ci ] + W i )
你會發(fā)現(xiàn),這個偽代碼與 01 背包問題的偽代碼只有 v 的循環(huán)次序不同而已怒见。
為什么這個算法就可行呢?首先想想為什么 01 背包中要按照 v 遞減的次序來循環(huán)姑宽。
讓 v 遞減是為了保證第 i 次循環(huán)中的狀態(tài) F [i, v] 是由狀態(tài) F [i ? 1, v ? Ci ] 遞推而來。
換句話說,這正是為了保證每件物品只選一次,保證在考慮“選入第 i 件物品”這件策略時,依據(jù)的是一個絕無已經(jīng)選入第 i 件物品的子結(jié)果 F [i ? 1, v ? Ci ] 舵变。而現(xiàn)在完全背包的特點恰是每種物品可選無限件,所以在考慮“加選一件第 i 種物品”這種策略時,卻正需要一個可能已選入第 i 種物品的子結(jié)果 F [i, v ? Ci ] ,所以就可以并且必須采用 v遞增的順序循環(huán)瘦穆。這就是這個簡單的程序為何成立的道理。
值得一提的是,上面的偽代碼中兩層 for 循環(huán)的次序可以顛倒绵咱。這個結(jié)論有可能會帶來算法時間常數(shù)上的優(yōu)化熙兔。
這個算法也可以由另外的思路得出艾恼。例如,將基本思路中求解 F [i, v ? Ci ] 的狀態(tài)轉(zhuǎn)移方程顯式地寫出來,代入原方程中,會發(fā)現(xiàn)該方程可以等價地變形成這種形式:
F [i, v] = max(F [i ? 1, v], F [i, v ? Ci ] + Wi )
2.6 小結(jié)
完全背包問題也是一個相當(dāng)基礎(chǔ)的背包問題,它有兩個狀態(tài)轉(zhuǎn)移方程拢切。希望讀者能
夠?qū)@兩個狀態(tài)轉(zhuǎn)移方程都仔細(xì)地體會,不僅記住,也要弄明白它們是怎么得出來的,
最好能夠自己想一種得到這些方程的方法秆吵。
事實上,對每一道動態(tài)規(guī)劃題目都思考其方程的意義以及如何得來,是加深對動態(tài)
規(guī)劃的理解、提高動態(tài)規(guī)劃功力的好方法主穗。
寒冰王座
#include <cstdio>
#include<algorithm>
#include<string.h>
#define Max(a,b) a>b?a:b
using namespace std;
int main()
{
int t;
int dp[10010],val[4]={0,150,200,350},vom[4]={0,150,200,350};
scanf("%d",&t);
while(t--)
{
int v;
scanf("%d",&v);
memset(dp,0,sizeof(dp));
for(int i=1;i<=3;i++)
{
for(int j=vom[i];j<=v;j++)
{
dp[j]=Max(dp[j],dp[j-vom[i]]+val[i]);
}
}
printf("%d\n",v-dp[v]);
}
}
