014-背包問題-動態規劃-《算法設計技巧與分析》M.H.A學習筆記
來源：程序員人生 發布時間：2016-07-07 19:17:58 閱讀次數：2520次
01背包：
01背包是在M件物品取出若干件放在空間為W的背包里，每件物品的體積為W1，W2……Wn，與之相對應的價值為P1,P2……Pn。求能取得的最大總價值。
基本思路：
V[i,j]表示從前i件物品中取出的，能裝入體積為j的背包的物品的最大總價值。
初始化條件：
V[i,0]和V[0,j]都為0，我們從其意義上就能夠理解。
狀態轉移方程：
V[i,j]=max{ V[i⑴,j]，V[i⑴,j-Wi]+Pi }
，前后分別為第i件物品不取和獲得情況。
總的就是下面的遞推式：
算法分析：
表的大小為n*C，所以算法的時間復雜度為Θ(nC)，經過1些修改空間復雜度可以控制在Θ(C)內。
偽代碼：
C++代碼：
1.Θ(nC)的空間。
for(int i=0;i<=V;i++) dp[0][i]=0; // 初始條件
for(int i=1;i<=n;i++){
for(int v=0; v<=C[i]⑴; v++){
dp[i][v]=dp[i⑴][v];
}
for(int v=C[i];v<=V;v++){
dp[i][v]=max(dp[i⑴][v],dp[i⑴][v-C[i]]+W[i])
}
}
cout<<dp[n][V]<<endl;
2.在空間上做1些優化，Θ(C)的空間。
for(int i=0;i<=V;i++) dp[i]=0; // 初始條件
for(int i=1;i<=n;i++){
for(int v=V;v>=C[i];v--){
dp[v]=max(dp[v],dp[v-C[i]]+W[i])
}
}
cout<<dp[V]<<endl;
空間優化的基本思路：
我們知道原來代碼中的2維數組的i是為了表示在前i個物品中做選擇，同時也標志第i個物品是不是已選取了。
每次決策的時候是決定第i個物品是不是要選取。比如，對dp[i⑴][v-ci]我們知道第i個物品并沒有選取，而對dp[i][v-ci]我們可以知道第i個物品已被選取了，我們每次自從前面1個狀態（i⑴）來決策第i個是不是要選。
而空間優化的代碼通過另外1套機制來保證1個物品只選1次。
我們可以看到第2個代碼中的v是按逆序循環的，這樣做是很有必要的：
這是由于要保證第i次循環中的狀態dp[v]是由狀態dp[v-c]遞推而來。換句話說，這正是為了保證每件物品只選1次，保證在斟酌“選入第i件物品”這件策略時，根據的是1個沒有已選入第i件物品的子結果dp[v-ci]（如果已選入了，即dp[v]已完成狀態轉移方程，不會再進行）。
完全背包問題：
有N件物品和1個容量為V的背包。放入第i件物品所耗的容量為Ci，得到的價值為Wi，但是同1件物品可以放入任意多件，問您最多可以取得多少價值。
（1）2維數組的做法：時間復雜度O(NVlog2(V/C[i]))
基本思路
這里與01背包不同的是每件物品可以選任意多件，我們只需要在狀態轉移方程上進行1些改動：
V[i][j]=max{ V[i⑴][j-k*c[i]]+k*w[i] | 0<=k*c[i]<=v }
這里的k表示的是第i件物品選取的數量，在程序中，我們只需為k多進行1個循環，并注意k的取值范圍，就能夠解決完全背包問題。
偽代碼：
F[0][] ← {0}
F[][0] ← {0}
for i←1 to N
do for j←1 to V
do for k←0 to j/C[i]
if(j >= k*C[i])
then F[i][k] ← max(F[i][k],F[i⑴][j-k*C[i]]+k*W[i])
return F[N][V]
（2）1維數組的做法：時間復雜度O(NV)
直接放代碼：
C++代碼：
for(int i=0;i<=V;i++) dp[i]=0; // 初始條件
for(int i=1;i<=n;i++){
for(int v=C[i];v<=V;v++){
dp[v]=max(dp[v],dp[v-C[i]]+W[i])
}
}
基本思路：
這里和01背包的空間優化代碼差不多，改變的是v的循環順序。前面v逆序循環的目的是為了保證每件物品只選擇1次，改成正序循環后，每件物品選擇的次數可以是任意的。
看下面這個例子dp[v-ci]后選擇了第i件物品變成dp[v]，而dp[(v+ci)-ci]依然可以選擇第i件物品，變成dp[v+ci]。
多重背包：
有N件物品和1個容量為V的背包。放入第i件物品所耗的容量為Ci，得到的價值為Wi，但是第i件物品最多可以放入Mi件，問您最多可以取得多少價值。
基本思路：
（1）2維數組的做法
與前面兩種背包的做法類似，只在狀態轉移方程上做1些更改。
dp[i][v]=max{ dp[i⑴][v-k*c[i]]+k*w[i] | 0<=k<=m[i] }
就不貼代碼了。
（2）轉化為01背包
空間優化的做法是將其轉化為01背包，并采取2進制的做法進行拆分，即拆分成1件、2件、4件...。
for(int i=1;i<＝n;i++){
int num=m[i]; // num為第i件物品由多少件
for(int k=1;num>=0;k*=2){
int mul=min(k,num) //k即為2進制數，之所以要和num取最小就類似與1000的時候512和489的情況，我們要選的時489.
for(int j=V;j>=C[i]*mul;j--){
dp[j]=max(dp[j],dp[j-C[i]*mul]+v[i]*mul)
}
num-=mul; // 分完那堆以后從總數上扣掉
}
}
最后貼1個代碼：
#include <iostream>
using namespace std;
const int N = 3;//物品個數
const int V = 8;//背包容量
int Weight[N + 1] = {0,1,2,2};
int Value[N + 1] = {0,6,10,20};
int Num[N + 1] = {0,10,5,2};
int f[V + 1] = {0};
/*
f[v]:表示把前i件物品放入容量為v的背包中取得的最大收益。
f[v] = max(f[v],f[v - Weight[i]] + Value[i]);
v的為逆序
*/
void ZeroOnePack(int nWeight,int nValue)
{
for (int v = V;v >= nWeight;v--)
{
f[v] = max(f[v],f[v - nWeight] + nValue);
}
}
/*
f[v]:表示把前i件物品放入容量為v的背包中取得的最大收益。
f[v] = max(f[v],f[v - Weight[i]] + Value[i]);
v的為增序
*/
void CompletePack(int nWeight,int nValue)
{
for (int v = nWeight;v <= V;v++)
{
f[v] = max(f[v],f[v - nWeight] + nValue);
}
}
int MultiKnapsack()
{
int k = 1;
int nCount = 0;
for (int i = 1;i <= N;i++)
{
if (Weight[i] * Num[i] >= V)
{
//完全背包:該類物品原則上是無窮供應，
//此時滿足條件Weight[i] * Num[i] >= V時，
//表示無窮量供應，直到背包放不下為止.
CompletePack(Weight[i],Value[i]);
}
else
{
k = 1;
nCount = Num[i];
while(k <= nCount)
{
ZeroOnePack(k * Weight[i],k * Value[i]);
nCount -= k;
k *= 2;
}
ZeroOnePack(nCount * Weight[i],nCount * Value[i]);
}
}
return f[V];
}
int main()
{
cout<<MultiKnapsack()<<endl;
system("pause");
return 1;
}
更進1步的了解，可以看看Tianyi Cui《背包問題9講》。
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
