※ 引述《yoco.bbs@bbs.wretch.cc (眠月..)》之銘言：
: ※ 引述《cplusplus.bbs@ptt.cc (永夜)》之銘言：
: > "0-1 knapsack"算是NPC中比較好解的問題了
: > 通常如果範圍不大的話 可以用DP的方式求解 實際上還有用的
: 我能不能請教一下 0-1 knapsack 問題要怎麼應用DP解 @_@？
: 我只知道有用DP解的方法 卻一直不知道是怎麼用上...
: 請教一下概念就好...
DP其實概念上也是暴力法的一種，只是會省掉很多重複的動作不做
所以可以省去很多時間做那些重複的事。
一個問題只要可以求出遞迴關係式，一般來說就可以應用DP來解。
簡單的例如 fibonacci sequence
f(i)= f(i-1)+f(i-2) for i>=2
1 for i=0,1
程式實做就像迴圈跑 f[i]=f[i-1]+f[i-2];
----------------------------------------------------------------------------
0-1 knapsack以裝最多最滿(總和最大)為目標的話，可以如下設計
T(i,r): 考慮完第 i 個物品後，可否產生總和為 r 的可能性。
true表示可以，false表示不可以。
T(i,r) = T(i-1,r-w[i]) || T(i-1,r) for i>=1, w[i]:weight of ith element
true for i=0,W=0 (initial condition)
false for i=0,W!=0 (initial condition)
T(i,r) = T(i-1,r-w[i]) || T(i-1,r)
^^^^^^^^^^^^^^^^^^^^^^^^^ take or not take 兩種情形
考慮完第i個物品總和是 r 的情形只有兩種，就是
1. 考慮完第(i-1)個時總和可能是 r-w[i] ，剛好加上第i個物品就是r-w[i]+w[i]=r
2 或是考慮完第(i-1)個時總和可能是 r ，而不加上第i個物品就是 r+0=r
當然 T(0,0) 就是 true ，表示尚未考慮任何物品時，總和為0是可能的，
其他不可能(false)。
因此當問題中有 K 個物品時，我們可以跑 K 次迴圈來完成這個DP動作...
以下是簡單實做
int weights[K];
int sum=0;
bool T[K+1][W+1]; // W是背包總容量
for(int i=0;i<K;i++)
{
for(int j=0;j<=sum && j<=W;j++)
if(T[i][j])
{
if(j+weight[i]<=W) T[i+1][j+weight[i]]=true; //take
T[i+1][j]=true; //not take
}
sum+=weight[i];
}
int answer=0;
for(int i=W;i>=0;i--)
if(T[K][i]){ answer=i; break; }
實做上有很多變化型，這只是其中一種最簡單的，僅供參考
講得不太清楚的話，請見諒，最近考試睡眠不足...
有興趣的話可以看看這一題 http://acm.uva.es/p/v104/10482.html
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.205.46
※ 編輯: cplusplus 來自: 140.115.205.46 (06/19 11:23)