最近在學習動態規劃，會了不少基礎的之后就開始挑戰比較困難的背包問題了，我這里自己寫了每一講的問題，解析，代碼，注釋。如果dp還沒入門的孩紙就去看看我的另一篇文章http://www.cnblogs.com/luyi14/p/4344946.html ? ?
第一講 ?0 ?1 ?背包
題目：
有N件物品和一個容量為V的背包。第i件物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使價值總和最大。
解析：
最基礎。
狀態：0不裝1裝，是0 1 背包
轉移方程：f[i][v] = max (f[i][v],f[i-1][v-c[i]]+w[i]);
一開始都看不懂這是什么玩意。變成一維的會好理解一點。看代碼：
1 #include<stdio.h> 2 #define max(a,b) a>b?a:b 3 int main() 4 { 5 int v,n; 6 while(~scanf("%d%d",&v,&n)) 7 { 8 int c[101]={0},w[101]={0},f[1001]={0},i,j,k; 9 //這里定義初始值也是為了解決另一種問題就是恰好裝滿背包 10 //初始值就是除了f【0】=0.別的均-無窮就好 11 //已經不用吧背包裝滿。就如上代碼 12 for(i = 1 ; i <= n ; i ++) 13 scanf("%d%d",&c[i],&w[i]); 14 for(i = 1 ; i <= n ; i++) 15 // 16 for(j = v;j >= c[i]; j--) 17 //優化 后面獲得的數值不會影響到前面的這是肯定的、 18 f[j] = max(f[j],f[j-c[i]]+w[i]); 19 //等于轉移方程 f[v] = max(f[i-1][v],f[i-1][v-c[i]); 20 printf("%d\n",f[v]); 21 } 22 return 0; 23 }
稍微先看看代碼再來看解析：
剛才的方程式非常重要建議要徹底理解，將前i 件物品放入容量為v 的背包中，這個子問題，如果只考慮第i件物品 的策略 （0 1）那么問題就簡化為前i -1 件物品放入的問題，（這里算是遞歸的思路吧不斷縮短）前i - 1個物體放入剩下容量為 v - c【i】 的背包中 ?這時候的最大價值就是
f[i][v-c[i]] 加上第i件物品的價值w[i];
這個確實很難理解。看看一維的代碼吧。
for i=1..N
??? for v=V..0
??????? f[v]=max{f[v],f[v-c[i]]+w[i]};
這里就是用f【】來保存每一個物品放不放所導致的結果，
話就不多說了。還是自己把過程模擬一遍，才能真正去理解算法中精妙的dp吧。
?
...)
