目錄：

• 動態規劃簡介
• 0-1 背包問題
• 完全背包問題
• 多重背包問題
• 混合背包問題
• 二維（多維）費用背包問題
• 分組的背包問題
• 有依賴的背包問題

動態規劃簡介

在學習背包問題之前需要對動態規劃有一定的了解 。一般來說，當一個最優決策問題可以劃分成規模更小的子問題，且具有最優子結構（即全局的最優解包含了子問題的最優解），則可以考慮用動態規劃算法。動態規劃的實質是分治思想和解決冗余，因此，動態規劃是一種將問題實例分解為更小的、相似的子問題，并存儲子問題的解而避免計算重復的子問題，以解決最優化問題的算法策略。由此可知，動態規劃法與分治法和貪心法類似，它們都是將問題實例歸納為更小的、相似的子問題，并通過求解子問題產生一個全局最優解。動態規劃法的關鍵就在于，對于重復出現的子問題，只在第一次遇到時加以求解，并把答案保存起來，讓以后再遇到時直接引用，不必重新求解。

動態規劃算法最重要的便是尋找狀態轉移方程，即多段決策過程的遞推關系。關于動態規劃的更多內容，我們以后會再總結。

今天我們來學習動態規劃的經典應用問題：背包問題。本文是對網上流傳多年的《背包問題九講》進行糾錯和補充，把其中講的模糊的地方清晰化，并加入了一些例題用c++實現。 文中出現的所有代碼均為本人編寫 ，歡迎指正。

• 0-1 背包問題

題目

有N件物品和一個容量為V的背包。第i件物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使價值總和最大。

把0-1背包問題抽象化（X1，X2，…，Xn，其中 Xi 取0或1，表示第 i 個物品選或不選），Vi表示第 i 個物品的價值，Wi表示第 i 個物品的體積（重量）；

b) 建立模型，即求max(V1X1+V2X2+…+VnXn)；

c) 約束條件，W1X1+W2X2+…+WnXn<capacity；

d) 定義V(i,j)：當前背包容量 j，前 i 個物品最佳組合對應的價值；

基本思路

這是最基礎的背包問題，特點是：每種物品僅有一件，可以選擇放或不放。

用子問題定義狀態：即f[i][v]表示前i件物品恰放入一個容量為v的背包可以獲得的最大價值。則其狀態轉移方程便是：

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

這個方程非常重要，基本上所有跟背包相關的問題的方程都是由它衍生出來的。所以有必要將它詳細解釋一下：“將前i件物品放入容量為v的背包中”這個子問題，若只考慮第i件物品的策略（放或不放），那么就可以轉化為一個只牽扯前i-1件物品的問題。如果不放第i件物品，那么問題就轉化為“前i-1件物品放入容量為v的背包中”，價值為f[i-1][v]；如果放第i件物品，那么問題就轉化為“前i-1件物品放入剩下的容量為v-c[i]的背包中”，此時能獲得的最大價值就是f[i-1][v-c[i]]再加上通過放入第i件物品獲得的價值w[i]。

優化空間復雜度

以上方法的時間和空間復雜度均為O(N*V)（）其中時間復雜度基本已經不能再優化了，但空間復雜度卻可以優化到O(V)。

先考慮上面講的基本思路如何實現，肯定是有一個主循環i=1..N，每次算出來二維數組f[i][0..V]的所有值。由于我們在計算f[i][v]時要用到f[i-1][v]和f[i-1][v-c[i]],因此要保證合適的計算順序。

如果只用一個數組f[0..V]，如何保證第i次循環結束后f[v]中表示的就是我們定義的狀態f[i][v]呢？事實上，這要求在每次主循環中我們以v=V..0的順序（逆序）推f[v]，這樣才能保證推f[v]時f[v-c[i]]保存的是狀態f[i-1][v-c[i]]的值。偽代碼如下：

for i=1..Nfor v=V..0f[v]=max{f[v],f[v-c[i]]+w[i]};//f[v]初始值為？

這段程序中，i從小往大遞增，對應的分f[v]其實隱式的具有i這一輪次信息，即第i 輪迭代完成后f[v]就是之前的f[i][v]。

其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相當于我們的轉移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}，因為現在的f[v-c[i]]就相當于原來的f[i-1][v-c[i]]。如果將v的循環順序從上面的逆序改成順序的話，那么則成了f[i][v]由f[i][v-c[i]]推知，與本題意不符，

事實上，使用一維數組解01背包的程序在后面會被多次用到，所以這里抽象出一個處理一件01背包中的物品過程，以后的代碼中直接調用不加說明。

過程ZeroOnePack，表示處理一件01背包中的物品，兩個參數cost、weight分別表明這件物品的費用和價值。

procedure ZeroOnePack(cost,weight)ZeroOnePack(c[i],w[i]);f[v]=max{f[v],f[v-cost]+weight}

注意這個過程里的處理與前面給出的偽代碼有所不同。前面的示例程序寫成v=V..0是為了在程序中體現每個狀態都按照方程求解了，避免不必要的思維復雜度。而這里既然已經抽象成看作黑箱的過程了，就可以加入優化。費用為cost的物品不會影響狀態f[0..cost-1]，這是顯然的，因為裝不進去。

有了這個過程以后，01背包問題的偽代碼就可以這樣寫：

for i=1..NZeroOnePack(c[i],w[i]);

初始化的細節問題

我們看到的求最優解的背包問題題目中，事實上有兩種不太相同的問法。有的題目要求“恰好裝滿背包”時的最優解，有的題目則并沒有要求必須把背包裝滿。一種區別這兩種問法的實現方法是在初始化的時候有所不同。

如果是第一種問法，要求恰好裝滿背包，那么在初始化時除了f[0]為0其它f[1..V]均設為-∞，這樣就可以保證最終得到的f[N]是一種恰好裝滿背包的最優解。

如果并沒有要求必須把背包裝滿，而是只希望價格盡量大，初始化時應該將f[0..V]全部設為0。

為什么呢？可以這樣理解：初始化的f數組事實上就是在沒有任何物品可以放入背包時的合法狀態。如果要求背包恰好裝滿，那么此時只有容量為0的背包可能被價值為0的nothing“恰好裝滿”，其它容量的背包均沒有合法的解，屬于未定義的狀態，它們的值就都應該是-∞了。如果背包并非必須被裝滿，那么任何容量的背包都有一個合法解“什么都不裝”，這個解的價值為0，所以初始時狀態的值也就全部為0了。

這個小技巧完全可以推廣到其它類型的背包問題，后面也就不再對進行狀態轉移之前的初始化進行講解。

如何根據表格復原答案？

以上的算法可給出背包的最大價值，卻還沒給出具體選擇那些物品可以獲得最大價值。由于空間復雜度優化后的算法只保存了當前的價值信息，丟失了之前的信息，故無法用來尋找最優解的組成。我們需要用未優化的算法來找解的組成。

根據填表的原理可以有如下的尋解方式：1) f(i,j)=f(i-1,j)時，說明沒有選擇第i個商品，則回到f(i-1,j)；2) f(i,j)=f(i-1,j-w(i))+w(i)實時，說明裝了第i個商品，該商品是最優解組成的一部分，隨后我們得回到裝該商品之前，即回到f(i-1,j-w(i))；3) 一直遍歷到i＝0結束為止，所有解的組成都會找到。

下面來看一道相關例題

你是一個專業的小偷，計劃偷竊沿街的房屋。每間房內都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。給定一個代表每個房屋存放金額的非負整數數組，計算你 不觸動警報裝置的情況下 ，一夜之內能夠偷竊到的最高金額。來源：力扣（LeetCode）鏈接：https://leetcode-cn.com/problems/house-robberclass Solution { public:int rob(vector<int>& nums) {if(nums.size()<1)return 0;if(nums.size()==1)return nums[0];int dp[nums.size()];//dp[i]表示前i間房子可以獲得的最大金額。dp[0]=nums[0];dp[1]=max(nums[1],nums[0]);for(int i=2;i<nums.size();i++){dp[i]=max(dp[i-1],dp[i-2]+nums[i]);//狀態轉移方程}return dp[nums.size()-1];} };

• 完全背包問題

題目

有N種物品和一個容量為V的背包，每種物品都有無限件可用。第i種物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。

基本思路

這個問題非常類似于01背包問題，所不同的是每種物品有無限件。也就是從每種物品的角度考慮，與它相關的策略已并非取或不取兩種，而是有取0件、取1件、取2件…… V/c[i]件。如果仍然按照解01背包時的思路，令f[i][v]表示前i種物品恰放入一個容量為v的背包的最大權值。仍然可以按照每種物品不同的策略寫出狀態轉移方程，像這樣：

f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}

這跟01背包問題一樣有O(N*V)個狀態需要求解，但求解每個狀態的時間已經不是常數了，求解狀態f[i][v]的時間是O(v/c[i])，總的復雜度是超過O(VN)的。

將01背包問題的基本思路加以改進，得到了這樣一個清晰的方法。這說明01背包問題的方程的確是很重要，可以推及其它類型的背包問題。但我們還是試圖改進這個復雜度。

//基本算法,已運行檢驗過。 #include<iostream> #include<vector> using namespace std; int completeKnapsak(vector<int>&w,vector<int>&c, int&volume){ vector<int>dp(volume+1,0); for(int i=0;i<w.size();i++) { for(int v=volume;v>=0;v--)//為什么逆序前面已經講過。{ for(int k=0;k*c[i]<=v;k++) { dp[v]=max(dp[v],dp[v-k*c[i]]+k*w[i]); } } } return dp[volume];} int main(){ int a[]={7,5,8,6,4,2,9}; vector<int>w(a,a+sizeof(a)/sizeof(int)); int b[]={2,1,5,3,7,4,8}; vector<int>c(b,b+sizeof(b)/sizeof(int)); int volume=15; cout<<completeKnapsak(w,c,volume); return 0;}

一個簡單有效的優化

完全背包問題有一個很簡單有效的優化，是這樣的：若兩件物品i、j滿足c[i]<=c[j]且w[i]>=w[j]（即i代價小而收益大），則將物品j去掉，不用考慮。這個優化的正確性顯然：任何情況下都可將價值小費用高得j換成物美價廉的i，得到至少不會更差的方案。對于隨機生成的數據，這個方法往往會大大減少物品的件數，從而加快速度。然而這個并不能改善最壞情況的復雜度，因為有可能特別設計的數據可以一件物品也去不掉。

這個優化可以簡單的O(N^2)地實現，一般都可以承受。另外，針對背包問題而言，比較不錯的一種方法是：首先將費用大于V的物品去掉，然后使用類似計數排序的做法，計算出費用相同的物品中價值最高的是哪個，可以O(V+N)地完成這個優化。

#include<iostream> #include<vector> #include<map> using namespace std;int completeKnapsak(vector<int>&w,vector<int>&c,int&volume){vector<int>dp(volume+1,0);map<int,int> resid;map<int,int>::iterator it;for(int i=0; i<c.size();i++)//成本相同時，保留收益最高者。{ if(c[i]>volume)continue;it=resid.find(c[i]);if(it==resid.end()) resid[c[i]]=w[i];else{resid[c[i]]=max(resid[c[i]],w[i]);}}for(map<int,int>::iterator id=resid.begin();id!=resid.end();id++){for(int v=volume;v>=0;v--)//為什么逆序前面已經講過。{for(int k=0;k*id->first<=v;k++){dp[v]=max(dp[v],dp[v-k*id->first]+k*id->second);}}}return dp[volume];}int main(){int a[]={7,5,8,6,4,2,9};vector<int>w(a,a+sizeof(a)/sizeof(int));int b[]={2,1,5,3,7,4,8};vector<int>c(b,b+sizeof(b)/sizeof(int))；int volume=15;cout<<completeKnapsak(w,c,volume);return 0; }

轉化為01背包問題求解

既然01背包問題是最基本的背包問題，那么我們可以考慮把完全背包問題轉化為01背包問題來解。最簡單的想法是，考慮到第i種物品最多選V/c[i]件，于是可以把第i種物品轉化為V/c[i]件費用及價值均不變的物品，然后求解這個01背包問題。這樣完全沒有改進基本思路的時間復雜度，但這畢竟給了我們將完全背包問題轉化為01背包問題的思路：將一種物品拆成多件物品。

更高效的轉化方法是：把第i種物品拆成費用為c[i]*2^k、價值為w[i]*2^k的若干件物品，其中k滿足c[i]*2^k<=V。這是二進制的思想，因為不管最優策略選幾件第i種物品，總可以表示成若干個2^k件物品的和。這樣把每種物品拆成O(log(V/c[i]))件物品，是一個很大的改進。

//用二進制的方法，我寫了兩個版本，在此均給出 #include<iostream> #include<vector> #include<cmath> using namespace std; int completeKnapsak_1(vector<int>&w,vector<int>&c, int&volume) {vector<int>dp(volume+1,0);vector<int>newc;vector<int>neww;int ni;for(int i=0;i<c.size();i++){ ni=volume/c[i];int k;for(k=0;(pow(2,k+1))<=ni;k++){ newc.push_back(c[i]*(pow(2,k))); neww.push_back(w[i]*pow(2,k)); } newc.push_back(c[i]*(ni-pow(2,k)+1)); neww.push_back(w[i]*(ni-pow(2,k)+1)); } for(int i=0;i<newc.size();i++) { for(int v=volume;v>=newc[i];v--) { dp[v]=max(dp[v],dp[v-newc[i]]+ neww[i]); } } return dp[volume];} int completeKnapsak_2(vector<int>&w,vector<int>&c, int&volume)//這個程序完成了和上面一樣的功能，但是節省了空間。 {vector<int>dp(volume+1,0);int ni;for(int i=0;i<c.size();i++){ni=volume/c[i];int k=1;while(k<ni){ for(int v=volume;v>=k*c[i];v--)//ZeroOnePack(k*w,k*c) { dp[v]=max(dp[v],dp[v-k*c[i]]+k*w[i]);}ni-=k;k*=2;}for(int v=volume;v>=ni*c[i];v--)//ZeroOnePack(ni*w,ni*c) { dp[v]=max(dp[v],dp[v-ni*c[i]]+ni*w[i]);}}return dp[volume]; }int main() { int a[]={7,5,8,6,4,2,9}; vector<int>w(a,a+sizeof(a)/sizeof(int)); int b[]={2,1,5,3,7,4,8}; vector<int>c(b,b+sizeof(b)/sizeof(int)); int volume=50; cout<<endl; cout<<completeKnapsak_2(w,c,volume); return 0;}

但我們有更優的O(VN)的算法。

O(VN)的算法

這個算法使用一維數組，先看偽代碼：

for i=1..Nfor v=0..Vf[v]=max{f[v],f[v-cost]+weight}

你會發現，這個偽代碼與01背包的偽代碼只有v的循環次序不同而已。為什么這樣一改就可行呢？首先想想為什么01背包中要按照v=V..0的逆序來循環。這是因為要保證第i次循環中的狀態f[i][v]是由狀態f[i-1][v-c[i]]遞推而來。換句話說，這正是為了保證每件物品只選一次，保證在考慮“選入第i件物品”這件策略時，依據的是一個絕無已經選入第i件物品的子結果f[i-1][v-c[i]]。而現在完全背包的特點恰是每種物品可選無限件，所以在考慮“加選一件第i種物品”這種策略時，卻正需要一個可能已選入第i種物品的子結果f[i][v-c[i]]，所以就可以并且必須采用v=0..V的順序循環。這就是這個簡單的程序為何成立的道理。

這個算法也可以以另外的思路得出。例如，基本思路中的狀態轉移方程可以等價地變形成這種形式：

f[i][v]=max{f[i-1][v],f[i][v-c[i]]+w[i]}

其實這個方程的本質就是，我們要在所有可能的情況中找到最優者（動態規劃就是一種聰明的窮舉法）。而對于第i步而言，在完全背包問題的語境下，只有兩種可能，要么一個都不選，要么至少選一個，分別對應f[i-1][v]和f[i][v-c[i]]+w[i]。

將這個方程用一維數組實現，便得到了上面的偽代碼。

最后抽象出處理一件完全背包類物品的過程偽代碼，以后會用到：

procedure CompletePack(cost,weight)for v=cost..Vf[v]=max{f[v],f[v-c[i]]+w[i]}#include<iostream> #include<vector> #include<cmath> using namespace std; int completeKnapsak(vector<int>&w,vector<int>&c, int&volume){ vector<int>dp(volume+1,0); for(int i=0;i<c.size();i++) { for(int v=c[i];v<=volume;v++) { dp[v]=max(dp[v],dp[v-c[i]]+w[i]); } } return dp[volume];} int main(){ int a[]={7,5,8,6,4,2,9}; vector<int>w(a,a+sizeof(a)/sizeof(int)); int b[]={2,1,5,3,7,4,8}; vector<int>c(b,b+sizeof(b)/sizeof(int)); int volume=15; cout<<endl; cout<<completeKnapsak(w,c,volume); return 0;}

完整內容可查看下面這篇推文：

https://mp.weixin.qq.com/s/c5Q23XscHf-MPQHjQVIKBQ?mp.weixin.qq.com

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的多维多重背包问题_满满干货！背包问题全总结（带c++源码）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。