動态規劃之背包
- 背景介紹
-
- 0-1背包問題
- 完全背包問題
- 多重背包
- 多重背包二進制優化
- 總結
背景介紹
動态規劃與貪心算法有相同之處，他們通常都是用來求解最優化的問題，但是貪心每次所得的都是局部最優，最終這個局部最優就是最終的答案，例如最小化找零問題，我們每次嘗試使用最大面值。相比與動規劃的問題，動态規劃問題通常具有這樣幾個特性。
1、具有子問題結構
2、從一個狀态轉移到另一個狀态
3、邊界條件
通常我們求解動态規劃都是根據這樣一些性質進行求解。下面主要講的是動态規劃裡面比較經典的背包問題。
0-1背包問題
問題描述
有 N 件物品和一個容量是 V 的背包。每件物品隻能使用一次。第 i 件物品的體積是 vi，價值是 wi。求解将哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價值最大。輸出最大價值。
輸入格式
第一行兩個整數，N，V，用空格隔開，分别表示物品數量和背包容積。接下來有 N 行，每行兩個整數 vi,wi，用空格隔開，分别表示第 i 件物品的體積和價值。
輸出格式
輸出一個整數，表示最大價值。
資料範圍
0<N,V≤1000
0<vi,wi≤1000
輸入樣例
4 5
1 2
2 4
3 4
4 5
輸出樣例
8
求解思路
對于動态規劃，首先可以思考如何描述狀态，假設我們用dp[i][j]描述在背包剩餘體積為j的情況下，選用前i件物品的最大價值。然後我們對于每件物品有兩種選擇選或者不選。不選擇第i件物品的情況下，dp[i][j] = dp[i-1][j],選擇第i件物品的時候，dp[i][j] = dp[i][j-v[i]]+w[i] (j>=v[i])。邊界條件可以直接全部初始化為0。
代碼實作
#include <iostream>
#include <cstring>
using namespace std;
/*
1、dp[i][j] = dp[i-1][j] 第i件物品不拿
2、dp[i][j] = max(dp[i][j],dp[i-1][j-v[i]]+w[i]) (j>=v[i])
*/
#define N 1010
int dp[N][N];//dp數組
int v[N],w[N];//體積，和價值
int n,m;
int main(){
cin>>n>>m;//物品數量 體積
for(int i = 1;i<=n;i++)
cin>>v[i]>>w[i];
for(int i = 1;i<=n;i++){
for(int j = 1;j<=m;j++){
dp[i][j] = dp[i-1][j];
if(j>=v[i]){
dp[i][j] = max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
}
}
}
int res = 0;
for(int i = 1;i<=m;i++){
res = max(res,dp[n][i]);
}
cout<<res<<endl;
}
優化
對于上述的二維數組表示，我們可以通過一維數組對其進行等價替換。我們在枚舉體積的時候從大到小枚舉，這樣就可以保證 dp[j] = max(dp[j],dp[j-v[i]]+w[i]); (j>=v[i],j從m開始)。
代碼實作
#include <iostream>
#include <cstring>
using namespace std;
#define N 1010
int dp[N];//dp數組
int v[N],w[N];//體積，和價值
int n,m;
int main(){
cin>>n>>m;//物品數量 體積
for(int i = 1;i<=n;i++)
cin>>v[i]>>w[i];
for(int i = 1;i<=n;i++){
for(int j = m;j>=v[i];j--){
dp[j] = max(dp[j],dp[j-v[i]]+w[i]);
}
}
cout<<dp[m]<<endl;
}
完全背包問題
完全背包問題與0-1背包問題的差別就在于物品可以拿的次數，如果是0-1背包，每件物品隻能拿一次，完全背包在不超過背包容量的情況下，無限次。這是兩者的根本差別。
問題描述
有 N 種物品和一個容量是 V 的背包，每種物品都有無限件可用。第 i 種物品的體積是 vi，價值是 wi。求解将哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價值最大。輸出最大價值。
輸入輸出與0-1背包一緻。
代碼實作
#include <iostream>
#include <cstring>
#include <algorithm>
/**
完全背包問題：
m:物品數 n：背包容量
dp[i] 容量為i的背包所裝的物品的最大價值
int res = max{dp[0]....dp[n]}
for(int i = 0;i<m;i++)
for(int j = n;j>=v[i];j--)
for(int k = 0;k*v[i]<=j;k++)
dp[j] = max(dp[j],dp[j-k*v[i]]+w[i]*k);
for(int i = 0;i<m;i++)
for(int j = v[i];j<=n;j--)
dp[j] = max(dp[j],dp[j-v[i]]+w[i]);
*/
using namespace std;
const int N = 1010;
int dp[N];
int m,n;
int main(){
cin>>m>>n; //物品數 容量
for(int i=0;i<m;i++)
{
int v,w;
cin>>v>>w;
for(int j = v;j<=n;j++){
dp[j] = max(dp[j],dp[j-v]+w);
}
}
cout<<dp[n]<<endl;
}
多重背包
問題描述
有 N 種物品和一個容量是 V 的背包。第 i 種物品最多有 si 件，每件體積是 vi，價值是 wi。求解将哪些物品裝入背包，可使物品體積總和不超過背包容量，且價值總和最大。輸出最大價值。
輸入格式
第一行兩個整數，N，V，用空格隔開，分别表示物品種數和背包容積。接下來有 N 行，每行三個整數 vi,wi,si，用空格隔開，分别表示第 i 種物品的體積、價值和數量。
輸出格式
輸出一個整數，表示最大價值。
資料範圍
0<N,V≤100
0<vi,wi,si≤100
輸入樣例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
輸出樣例
10
求解思路
多重背包可以拆成多個0-1背包，對于每一個物品在沒有達到背包容量之前我們都可以有0-到s中選擇，也就是也可選擇0件，1件，2件。。。s件。可以0-1背包的基礎上加上一層for循環枚舉一下物品數。
代碼實作
#include <iostream>
#include <algorithm>
#include <cstring>
/**
n重背包問題
選的個數有限制，未優化的多重背包
狀态
dp[i] 體積為i的情況下，最大價值
max{dp[0]....dp[n]}
for(int i = 0;i<m;i++)
for(int j = n;j>=v[i];j--)
for(int k = 0;k*v[i]<=n;k++){
dp[j] = max(dp[j],dp[j-k*v[i]]+k*w[i])
}
*/
using namespace std;
const int N = 110;
int v[N],w[N],s[N],dp[N];
int main(){
int m,n;
cin>>m>>n;
for(int i = 1;i<=m;i++){
cin>>v[i]>>w[i]>>s[i];
}
for(int i = 1;i<=m;i++){
for(int j = n;j>=0;j--){
for(int k = 1;k*v[i]<=j&&k<=s[i];k++){
dp[j] = max(dp[j],dp[j-k*v[i]]+k*w[i]);
}
}
}
cout<<dp[n]<<endl;
return 0;
}
多重背包二進制優化
對于上述多重背包問題求解過程中使用了三重for循環，對于事件複雜度要求高的化，我們需要進行優化。優化的過程主要是拆分，假設物品體積為7，對于0-7我們可以使用1 2 4三個數表示出來。
代碼實作
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
/**
多重背包問題二進制優化，
多重背包轉化成0-1背包
*/
const int N = 2010;
int dp[N];
int m,n;
struct Bag{
int v;
int w;
};
int main(){
vector<Bag> bags;
cin>>m>>n;
for(int i = 0;i<m;i++)
{
int v,w,s;
cin>>v>>w>>s;
for(int k = 1;k<=s;k*=2){
s -= k;
bags.push_back({v*k,w*k});
}
if(s>0){
bags.push_back({s*v,s*w});
}
}
for(int i = 0;i<bags.size();i++){
for(int j = n;j>=bags[i].v;j--){
dp[j] = max(dp[j],dp[j-bags[i].v]+bags[i].w);
}
}
cout<<dp[n]<<endl;
return 0;
}
總結
對于背包問題的求解，0-1背包問題是基礎。在0-1背包的問題上進行擴充。确定好狀态轉移方程。以及邊界條件。
![【資料結構】 醫院選址[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)