動態規劃01背包演算法
『壹』 java語言,背包問題,從Excel表中讀取數據
基本概念
問題雛形
01背包題目的雛形是:
有N件物品和一個容量為V的背包。第i件物品的體積是c[i],價值是w[i]。求解將哪些物品裝入背包可使價值總和最大。
從這個題目中可以看出,01背包的特點就是:每種物品僅有一件,可以選擇放或不放。
其狀態轉移方程是:
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
對於這方方程其實並不難理解,方程之中,現在需要放置的是第i件物品,這件物品的體積是c[i],價值是w[i],因此f[i-1][v]代表的就是不將這件物品放入背包,而f[i-1][v-c[i]]+w[i]則是代表將第i件放入背包之後的總價值,比較兩者的價值,得出最大的價值存入現在的背包之中。
理解了這個方程後,將方程代入實際題目的應用之中,可得
for (i = 1; i <= n; i++)
for (j = v; j >= c[i]; j--)//在這里,背包放入物品後,容量不斷的減少,直到再也放不進了
f[i][j] = max(f[i - 1][j], f[i - 1][j - c[i]] + w[i]);
問題描述
求出獲得最大價值的方案。
注意:在本題中,所有的體積值均為整數。
演算法分析
對於背包問題,通常的處理方法是搜索。
用遞歸來完成搜索,演算法設計如下:
int make(int i, int j)//處理到第i件物品,剩餘的空間為j 初始時i=m , j=背包總容量
{
if (i == 0) return 0;
if (j >= c[i])//(背包剩餘空間可以放下物品 i )
{
int r1 = make(i - 1, j - w[i]);//第i件物品放入所能得到的價值
int r2 = make(i - 1, j);//第i件物品不放所能得到的價值
return min(r1, r2);
}
return make(i - 1, j);//放不下物品 i
}
這個演算法的時間復雜度是O(n^2),我們可以做一些簡單的優化。
由於本題中的所有物品的體積均為整數,經過幾次的選擇後背包的剩餘空間可能會相等,在搜索中會重復計算這些結點,所以,如果我們把搜索過程中計算過的結點的值記錄下來,以保證不重復計算的話,速度就會提高很多。這是簡單的「以空間換時間」。
我們發現,由於這些計算過程中會出現重疊的結點,符合動態規劃中子問題重疊的性質。
同時,可以看出如果通過第N次選擇得到的是一個最優解的話,那麼第N-1次選擇的結果一定也是一個最優解。這符合動態規劃中最優子問題的性質。
解決方案
考慮用動態規劃的方法來解決,這里的:
階段:在前N件物品中,選取若干件物品放入背包中
狀態:在前N件物品中,選取若干件物品放入所剩空間為W的背包中的所能獲得的最大價值
決策:第N件物品放或者不放
由此可以寫出動態轉移方程:
我們用f[i][j]表示在前 i 件物品中選擇若干件放在已用空間為 j 的背包里所能獲得的最大價值
f[i][j] = max(f[i - 1][j - W[i]] + P[i], f[i - 1][j]);//j >= W[ i ]
這個方程非常重要,基本上所有跟背包相關的問題的方程都是由它衍生出來的。所以有必要將它詳細解釋一下:「將前i件物品放入容量為v的背包中」這個子問題,若只考慮第i件物品的策略(放或不放),那麼就可以轉化為一個只牽扯前i-1件物品的問題。如果不放第i件物品,那麼問題就轉化為「前i-1件物品放入容量為v的背包中」,價值為f[v];如果放第i件物品,那麼問題就轉化為「前i-1件物品放入已用的容量為c的背包中」,此時能獲得的最大價值就是f[c]再加上通過放入第i件物品獲得的價值w。
這樣,我們可以自底向上地得出在前M件物品中取出若干件放進背包能獲得的最大價值,也就是f[m,w]
演算法設計如下:
int main()
{
cin >> n >> v;
for (int i = 1; i <= n; i++)
cin >> c[i];//價值
for (int i = 1; i <= n; i++)
cin >> w[i];//體積
for (int i = 1; i <= n; i++)
f[i][0] = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= v; j++)
if (j >= w[i])//背包容量夠大
f[i][j] = max(f[i - 1][j - w[i]] + c[i], f[i - 1][j]);
else//背包容量不足
f[i][j] = f[i - 1][j];
cout << f[n][v] << endl;
return 0;
}
由於是用了一個二重循環,這個演算法的時間復雜度是O(n*w)。而用搜索的時候,當出現最壞的情況,也就是所有的結點都沒有重疊,那麼它的時間復雜度是O(2^n)。看上去前者要快很多。但是,可以發現在搜索中計算過的結點在動態規劃中也全都要計算,而且這里算得更多(有一些在最後沒有派上用場的結點我們也必須計算),在這一點上好像是矛盾的。
『貳』 用動態規劃演算法怎樣求解01背包問題
動態規劃主要解決的是多階段的決策問題。
01背包中,狀態為背包剩餘的容量,階段是每一個物品,決策是是否選擇當前的物品。
所以用動態規劃來解決是非常貼切的。
我們設f[V]表示已經使用容量為V時所能獲得的最大價值,w[i]表示i物品的質量,c[i]表示i物品的價值。
for(inti=1;i<=n;i++)
for(intj=V;j>=w[i];j--)
f[j]=max(f[j],f[j-w[i]]+c[i]);
這便是所謂的一個狀態轉移方程。
f[j]表示在已經使用容量為j時的最大價值,f[j-w[i]]表示在已經使用容量為j-w[i]時的最大價值。
f[j]可以由f[j-w[i]]這個狀態轉移到達,表示選取w[i]這個物品,並從而獲得價值為c[i]。
而每次f[j]會在選與不選中決策選出最優的方案。
從每一個物品,也就是每一個階段的局部最優推出最後的全局最優值。這樣就解決了01背包問題