背包問題
- 0/1背包
-
- 原理
- 輸出方案
- 例題HDU-2602
- 空間優化-滾動數組
- 完全背包
-
- 轉換為0/1背包
- 二維
- 一維
- 例題HDU-2159
- 多重背包
-
- 轉換為0/1背包
- 二進制拆分優化
- 例題HDU-2844
- 單調隊列優化
- 混合背包
背包問題：有多個重量不同、價值不同的物品，以及一個容量有限的背包，選擇一些物品裝入背包，求最大總價值。
背包問題無法用貪心求最優解，是典型的動态規劃問題。背包問題還可以分成3種：① 0-1背包、② 完全背包、③ 多重背包。
| 差別 | |
|---|---|
| 0/1背包 | 每種物品是一件 |
| 完全背包 | 每種物品是無限件 |
| 多重背包 | 每種物品是有限件 |
0/1背包
0/1背包顧名思義就是0和1兩種狀态，即每個物品裝入和不裝入背包這兩種狀态，如果不懂dp的話，可能用dfs的做法深搜，但時間複雜度是2n，肯定是不能接受的，或者用貪心，但也并不能得到全局最優解。下面舉例說明dp。
原理
假設4個物品，重量分别是w={2,3,6,5}，價值分别是v={6,3,5,4}，背包容量為9。
引進二維表dp[][]，dp[i][j]表示考慮前i個物品裝入容量為j的背包中獲得的最大價值。可以把每個dp[i][j]都看成一個背包。
步驟一：隻裝第1個物品
因為物品1的重量是2，是以容量小于2的背包都放不進去（即dp[1][0]=dp[1][1]=0），在容量2時裝入，其價值是物品1的價值（即dp[1][2]=6），容量大于2的背包，多餘的容量也用不到（因為現在隻考慮物品1），其價值也都是6，如下圖
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|
| 1 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 |
步驟二：隻裝前2個物品
首先，物品2重量是3，背包容量3的情況和隻裝物品1情況一樣。下面從dp[2][3]開始填，此時我們可以選擇裝物品2，也可以不裝。
如果裝，那麼相當于把dp[i-1][j-3]的最大價值加上物品2的價值3，即考慮隻第一個物品的時候，騰出3容量放物品2，此時價值=3；
如果不裝，那麼相當于隻把物品1裝入，此時價值=6；
我們取兩者最大值，即dp[2][3]=max(3,6)=6。
後面的多餘容量同理。
三.重複上述步驟，得到dp數組
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|
| 1 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 |
| 2 | 6 | 6 | 6 | 9 | 9 | 9 | 9 | 9 |
| 3 | 6 | 6 | 6 | 9 | 9 | 9 | 11 | 11 |
| 4 | 6 | 6 | 6 | 9 | 9 | 10 | 11 | 11 |
最後答案是dp[4][9]，即把4個物品裝入容量為9的背包，最大價值是11。
輸出方案
現在回過頭看裝了哪些物品：
dp[4][9]=max(dp[3][4]+4，dp[3][9])=dp[3][9]，說明沒有裝物品4；
dp[3][9]=max(dp[2][3]+5，dp[2][9])=dp[2][3]+5,說明裝了物品3；
以此類推，如圖箭頭所示，即裝了物品1和3，輸出方案即可。
除了這樣倒推外，也可以定義數組path[][]，path[i][j]表示狀态j下物品i是否被選中，初始化為0，置1表示選中，當更新dp的時候同時維護即可。
例題HDU-2602
HDU-2602 Bone Collector
說了這麼多可能有點迷，看下例題和代碼可能更易了解。
Problem Description
Many years ago , in Teddy’s hometown there was a man who was called “Bone Collector”. This man like to collect varies of bones , such as dog’s , cow’s , also he went to the grave …
The bone collector had a big bag with a volume of V ,and along his trip of collecting there are a lot of bones , obviously , different bone has different value and different volume, now given the each bone’s value along his trip , can you calculate out the maximum of the total value the bone collector can get ?
Input
The first line contain a integer T , the number of cases.
Followed by T cases , each case three lines , the first line contain two integer N , V, (N <= 1000 , V <= 1000 )representing the number of bones and the volume of his bag. And the second line contain N integers representing the value of each bone. The third line contain N integers representing the volume of each bone.
Output
One integer per line representing the maximum of the total value (this number will be less than 231).
Sample Input
1
5 10
1 2 3 4 5
5 4 3 2 1
Sample Output
14
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 1003;
int t, n, m;
int dp[maxn][maxn], v[maxn], w[maxn], path[maxn][maxn];
int main() {
scanf("%d", &t);
while (t--) {
memset(dp, 0, sizeof(dp));
//memset(path, 0, sizeof(path));
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)scanf("%d", &v[i]);
for (int i = 1; i <= n; i++)scanf("%d", &w[i]);
for (int i = 1; i <= n; i++)
for (int j = 0; j <= m; j++)
if (w[i] > j) //目前容量j小于物品i的重量，裝不下
dp[i][j] = dp[i - 1][j];
else { //可以裝，取不裝和裝的最大值
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
//if (dp[i - 1][j - w[i]] + v[i] > dp[i - 1][j])//記錄路徑
// path[i][j] = 1;
}
printf("%d\n", dp[n][m]);
/*for (int i = n, j = m; i >0 && j > 0;i--) { //輸出方案
if (path[i][j]) {
printf("%d ", i);
j -= w[i];
}
}*/
}
return 0;
} 複制
空間優化-滾動數組
如果資料很大的時候，我們無法定義這麼大的二維表，那麼就要考慮對空間複雜度進行優化。我們觀察上述二維表dp[][]，不難發現，每一行是從上一行算出來的，隻與上一行有關系，與更前面的行沒有關系。那麼用新的一行覆寫原來的就好了(就是一行數組進行滾動)，空間複雜度從O(NV)減少為O(V)。
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 1003;
int t, n, m;
int dp[maxn], v[maxn], w[maxn];
int main() {
scanf("%d", &t);
while (t--) {
memset(dp, 0, sizeof(dp));
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)scanf("%d", &v[i]);
for (int i = 1; i <= n; i++)scanf("%d", &w[i]);
for (int i = 1; i <= n; i++)
for (int j = m; j >= w[i]; j--)
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
printf("%d\n", dp[m]);
}
return 0;
} 複制
注意j應該逆序循環，即從後面往前面覆寫，不然會多次考慮每件物品（恰恰是完全背包的解），但我們不能重複選擇已經選擇的物品。不過，滾動數組覆寫掉了中間轉移狀态，無法倒推輸出方案，如果用path[][]記錄就沒有優化的意義了。
如果實在不了解為什麼逆序的話（剛開始的确費勁 ），不妨就定義pre[]表示上一行：
for (int i = 1; i <= n; i++) {
for (int j = w[i]; j <= m; j++)
dp[j] = max(pre[j], pre[j - w[i]] + v[i]);
memcpy(pre, dp, sizeof(dp));
} 複制
如果memcpy卡逾時，定義dp[2][n]交替即可。
完全背包
完全背包與0/1背包不同就是每種物品可以多次/無限選擇，而0/1背包的每種物品至多隻能選擇一次。
轉換為0/1背包
不難發現，完全背包其實可以轉換成0/1背包，第i種物品的出現次數至多是背包容量m/物品i重量w[i]，那麼以此建構新的v[]和w[]即可，也可以再加一層循環表示物品個數，然後套用0/1背包。
二維
0/1背包轉移方程是dp[i][j] = max(dp [i - 1] [j]，dp[i - 1][j - w[i]] + v[i])，即決策dp[i][j]（前i個物品，j容量時）是從前一行隻考慮前i-1個物品的情況下為基礎，避免重複選擇。而完全背包可以多次選擇第i個物品，是以是考慮前i個物品的情況下為基礎來決策，即同一行，推出轉移方程：dp[i][j] = max(dp [i] [j]，dp[i - 1][j - w[i]] + v[i])
for (int i = 1; i <= n; i++)
for (int j = w[i]; j <= m; j++)
dp[i][j] = max(dp[i][j],dp[i - 1][j - w[i]] + v[i]) 複制
一維
完全背包是順序，順序會覆寫以前的狀态，即存在選擇多次的情況。
for (int i = 1; i <= n; i++)
for (int j = w[i]; j <= m; j++)
dp[j] = max(dp[j], dp[j - w[i]] + v[i]); 複制
例題HDU-2159
HDU-2159 FATE
Problem Description
最近xhd正在玩一款叫做FATE的遊戲，為了得到極品裝備，xhd在不停的殺怪做任務。久而久之xhd開始對殺怪産生的厭惡感，但又不得不通過殺怪來升完這最後一級。現在的問題是，xhd升掉最後一級還需n的經驗值，xhd還留有m的忍耐度，每殺一個怪xhd會得到相應的經驗，并減掉相應的忍耐度。當忍耐度降到0或者0以下時，xhd就不會玩這遊戲。xhd還說了他最多隻殺s隻怪。請問他能升掉這最後一級嗎？
Input
輸入資料有多組，對于每組資料第一行輸入n，m，k，s(0 < n,m,k,s < 100)四個正整數。分别表示還需的經驗值，保留的忍耐度，怪的種數和最多的殺怪數。接下來輸入k行資料。每行資料輸入兩個正整數a，b(0 < a,b < 20)；分别表示殺掉一隻這種怪xhd會得到的經驗值和會減掉的忍耐度。(每種怪都有無數個)
Output
輸出升完這級還能保留的最大忍耐度，如果無法升完這級輸出-1。
Sample Input
10 10 1 10
1 1
10 10 1 9
1 1
9 10 2 10
1 1
2 2
Sample Output
-1
1
忍耐度->容量，經驗值->價值，同時再維護sum[]記錄個數，輸出達到價值n後的最大剩餘容量。
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 102;
int n, m, k, s;
int v[maxn], w[maxn], dp[maxn], sum[maxn];
int main() {
while (~scanf("%d%d%d%d", &n, &m, &k, &s)) {
for (int i = 1; i <= k; i++)
scanf("%d%d", &v[i], &w[i]);
memset(dp, 0, sizeof(dp));
memset(sum, 0, sizeof(sum));
for(int i=1;i<=k;i++)
for (int j = w[i]; j <= m; j++) {
if (sum[j - w[i]] + 1 > s)continue;
if (dp[j] < dp[j - w[i]] + v[i]) {
dp[j] = dp[j - w[i]] + v[i];
sum[j] = sum[j - w[i]] + 1;
}
}
int ans = -1;
for (int i = 1; i <= m; i++)
if (dp[i] >= n) {
ans = m - i;
break;
}
printf("%d\n", ans);
}
return 0;
} 複制
多重背包
多重背包比完全背包多了一個限制，即每種物品有個數限制，不再是無限。
轉換為0/1背包
同樣的，和完全背包一樣進行轉換，加循環或者重新建構即可，注意個數限制，可能逾時 。
二進制拆分優化
仔細思考，不難發現我們做了大量重複性的工作，比如同種物品的不同個體，比如第1種物品有3個，編号a,b,c，那麼選ab，ac，bc其實是等效的。我們可以通過「二進制分組」的方式優化拆分，一個數n可以拆分為k個數字，k=⌊log(n+1)⌋，複雜度為O（NMΣlogni）。
- n=20 +21 +22 +…+2k-1+n−2k+1
- 6=1+2+3
- 13=1+2+4+6
-
31=1+2+4+8+16
由這k個數字可以組成1~n的所有數值，這樣就能表示所有等效選擇方式了，即n個物品拆分成log(n)個物品，然後愉快的套0/1背包就好了。
例題HDU-2844
HDU-2844 Coins
Problem Description
Whuacmers use coins.They have coins of value A1,A2,A3…An Silverland dollar. One day Hibix opened purse and found there were some coins. He decided to buy a very nice watch in a nearby shop. He wanted to pay the exact price(without change) and he known the price would not more than m.But he didn’t know the exact price of the watch.
You are to write a program which reads n,m,A1,A2,A3…An and C1,C2,C3…Cn corresponding to the number of Tony’s coins of value A1,A2,A3…An then calculate how many prices(form 1 to m) Tony can pay use these coins.
Input
The input contains several test cases. The first line of each test case contains two integers n(1 ≤ n ≤ 100),m(m ≤ 100000).The second line contains 2n integers, denoting A1,A2,A3…An,C1,C2,C3…Cn (1 ≤ Ai ≤ 100000,1 ≤ Ci ≤ 1000). The last test case is followed by two zeros.
Output
For each test case output the answer on a single line.
Sample Input
3 10
1 2 4 2 1 1
2 5
1 4 2 1
0 0
Sample Output
8
4
沒有給重量，令重量=價值。
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 100005;
int n, m, cnt;
int value[102], num[102];
int dp[maxn], v[maxn];
int main() {
while (~scanf("%d%d", &n, &m) && n && m) {
memset(dp, 0, sizeof(dp));
cnt = 0;
for (int i = 1; i <= n; i++)scanf("%d", &value[i]);
for (int i = 1; i <= n; i++) {
scanf("%d", &num[i]);
for (int j = 1; j <= num[i]; j *=2) { //二進制拆分優化
v[++cnt] = value[i] * j;
num[i] -= j;
}
if (num[i])v[++cnt] = value[i] * num[i];
}
for (int i = 1; i <= cnt; i++)
for (int j = m; j >= v[i]; j--)
dp[j] = max(dp[j], dp[j - v[i]] + v[i]);
int ans = 0;
for (int i = 1; i <= m; i++)
if (dp[i] == i)ans++;
printf("%d\n", ans);
}
return 0;
} 複制
單調隊列優化
其實用二進制拆分就能AC絕大部分題了，但一些卡時間的題還是會TLE，用單調隊列優化可以使複雜度降為O(NM)。
從狀态轉移方程入手，假設第i種物品重量w，價值v，數量num，背包容量m
-
dp[i][j]=max(dp[i−1][j−w∗k]+v∗k)，k<=min(num，m/w)
把目前容量j分成w組（0,1,…w-1)，令d=j%w，s=j/w，推出
-
dp[i][j]=max(dp[i−1][d+w∗k]−v∗k)+v∗s
每組互不影響，枚舉餘數d，對每個餘數d都用單調隊列優化。
看代碼好了，免得誤人子弟
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 100005;
int n, m, cnt;
int v[102], num[102], dp[maxn];
struct Queue {
int pos, val;
}q[maxn];
int main() {
while (~scanf("%d%d", &n, &m) && n && m) {
memset(dp, 0, sizeof(dp));
cnt = 0;
for (int i = 1; i <= n; i++)scanf("%d", &v[i]);
for (int i = 1; i <= n; i++) {
scanf("%d", &num[i]);
if (v[i] * num[i] >= m) { //大于背包容量相當于完全背包
for (int j = v[i]; j <= m; j++)
dp[j] = max(dp[j], dp[j - v[i]] + v[i]);
continue;
} //單調隊列優化
for (int d = 0; d < v[i]; d++){ //枚舉餘數
int head = 1, rear = 0;
for (int j = 0; j <= (m - d) / v[i]; j++){
int cur = dp[j * v[i] + d] - j * v[i];
while (head <= rear && q[head].pos < j - num[i]) head++;
while (head <= rear && q[rear].val < cur) rear--;
q[++rear].val = cur;
q[rear].pos = j;
dp[j * v[i] + d] = q[head].val + j * v[i];
}
}
}
int ans = 0;
for (int i = 1; i <= m; i++)
if (dp[i] == i)ans++;
printf("%d\n", ans);
}
return 0;
} 複制
感受一下時間差
二進制：
單調隊列：
混合背包
就是混合上述三種背包，每種物品件數是一件、多件或無數件，判斷再調用對應模闆就好了。
背包問題還有分組背包，依賴背包等，最近一直在刷題，這篇部落格也是放在草稿箱裡好久了，留個位置以後更新吧(咕咕咕)
原創不易，請勿轉載（本不富裕的通路量雪上加霜 ）
部落客首頁：https://blog.csdn.net/qq_45034708