【算法速成課2 | 題單】背包問題

專欄指路：《算法速成課》

前導：

動態規劃問題中最入門、也最多變的，當屬背包問題。

簡單來說，就是在有限的空間，（花費最小的代價）達成最大的收益。

本文會講一些常見的背包問題（可通過目錄挑選題目），難度普及提高左右，配套一些例題。

個人認為比 oiwiki 更適合初學者一點，不過肯定沒人家全。

（1）0/1 背包

有 n?個物品，每個物品的重量為 $a_i$ 。

我們有一個最大承重為 v?的背包。

從 n?個物品中選若干個裝入背包，使得所選物品的和 s?盡量接近 v? $(s\leq v)$ ，即 v - s?的值最小。

標題的 0 和 1 指的是每個物品有不選和選兩種狀態。

根據這個定義狀態 f[i] 為 1 就表示背包里放 i 重量是可能的，0 則不可能。

代碼：

#include<bits/stdc++.h>
using namespace std;int a[30];
bool f[20010];   //f[i]：1 表示背包里放 i重量是可能的，0 則不可能 
//要多開一點空間，以防爆炸 int main() {ios::sync_with_stdio(false);   //關同步流，可以讓 cin更快一點 cin.tie(0);   //打了這兩行就不可以用 scanf和 printf了 int V, n;cin >> V >> n;for (int i = 1; i <= n; i++) {cin >> a[i];    //讀入 }memset(f, 0, sizeof(f));   //初始化 f[0] = 1;           //一開始背包里啥也沒有，0 是可能的 for (int i = 1; i <= n; i++) {for (int j = V; j >= a[i]; j--) {   //因為每個東西只有一個，所以要反著放//正著放就可以一種東西疊加，適合一個東西有無限個的情況 if (f[j - a[i]] == 1) {f[j] = 1;   //如果 j - a[i]是可能的，那么再放一個 a[i]也是可能的 }}}int p;for (int i = V; i >= 0; i--) {  //找最大的那個可能的 if (f[i] == 1) {p = i;break;}}cout << V - p << "\n";   //輸出差值 return 0;
}

例題：

洛谷 P2925 [USACO08DEC] Hay For Sale S

例題可以和上面代碼一樣做，但還可以有一種寫法：

#include <bits/stdc++.h>
using namespace std;int f[50010], a[5010];
//f[i]：表示給你 i空間，你最多可以放多少
//f[i] <= i int main() {ios::sync_with_stdio(false);cin.tie(0);int V, n; cin >> V >> n;for (int i = 1; i <= n; i++) {cin >> a[i];    //讀入 }memset(f, 0, sizeof(f));for (int i = 1; i <= n; i++) {for (int j = V; j >= a[i]; j--) {f[j] = max(f[j], f[j - a[i]] + a[i]);}}cout << f[V];//輸出給你 V空間，最多可以放多少return 0;
}

練習：

有 T?個數列。設 $S_i$ ?為從第 i?個數列選若干個數的和。

（當然，一個數列有很多個 $S_i$ ）

設整數 K?滿足所有數列 $S_i$ 中都有 K，求 K?的最大值。

解析：

每個數列都搞一個 0/1 背包，如果這個數列可以達到 i 那么 sum[i]++。

最后找最大的 i 滿足 sum[i] = T。

代碼就不給了。

例題 2：

小明背著一個背包（最大能帶的重量為 T）走進一個山洞。

山洞里有 n?個寶石，第 i?個寶石的重量為 $t_i$ ，拿到寶石店能賣 $m_i$ ?塊錢。

求最多能賣多少錢。

基本和之前的代碼一樣，只不過定義狀態 f[i] 為給你 i 空間，你最多可以賣多少錢。

核心代碼：

for (int i = 1; i <= n; i++) {for (int j = T; j >= t[i]; j--) {f[j] = max(f[j], f[j - t[i]] + m[i]);}
}cout << f[T] << "\n";

例題 3（有點難）：

洛谷P3010 [USACO11JAN] Dividing the Gold S

其實很簡單，想不通的話看代碼一下就懂了。

就是模數模完可能是零有點惡心：

#include<bits/stdc++.h>
using namespace std;const int N = 310, M = 6e5 + 10;   //最多就是 n * a[i]
const int P = 1000000;int a[N], f[M];  //f[i]: 有多少種加數方案能得到 i
bool g[M]; //g[i]: 0不可能，1可能
//因為對 1,000,000 取余完可能為 0，所以要多開一個 g 數組判斷當前 i 是否能得到int main() {ios::sync_with_stdio(false);cin.tie(0);int n;cin >> n;int sum = 0;for (int i = 1; i <= n; i++) {cin >> a[i];sum += a[i];}memset(f, 0, sizeof(f));memset(g, 0, sizeof(g));f[0] = 1;g[0] = 1;for (int i = 1; i <= n; i++) {for (int j = sum; j >= a[i]; j--) {f[j] = ( f[j] + f[j - a[i]] ) % P;g[j] |= g[j - a[i]] ;//位運算，如果 g[j - a[i]]等于 1 那么g[j] 也等于 1//反之 g[j] 不變}}for (int i = sum / 2; i >= 0; i--) {if (g[i] != 0) {  // i 可以達到cout << (sum - i) - i << "\n";   // sum - i 是另一組數長度 cout << f[i] << "\n";break;}}return 0;
}

（2）完全背包

有 n 種物品，每種物品的重量為 $a_i$ ，有無限個。

我們有一個最大承重為 v?的背包。

從 n 種物品中選若干個裝入背包，使得所選物品的和 s?盡量接近 v? $(s\leq v)$ ，即 v - s?的值最小。

輸入第 i?種寶石的重量為 $t_i$ ，拿到寶石店能賣 $m_i$ ?塊錢。

和上面 0/1 背包的例題 2 一模一樣，除了物品有無窮多個。

那么第二個循環就變成正序。

代碼：

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;int t[N], m[N];
int f[N];int main() {ios::sync_with_stdio(false);cin.tie(0);int T, n;cin >> T >> n;for (int i=1; i<=n; i++) {cin >> t[i] >> m[i];}memset(f, 0, sizeof(f)); for (int i = 1; i <= n; i++) {for (int j = t[i]; j <= T; j++) {    //就是這里！！改成正序的，就代表單種物品可以自己和自己疊加f[j] = max(f[j], f[j - t[i]] + m[i]);}}cout << f[T] << "\n";return 0;
}

稍有難度的例題：

洛谷 P3027 [USACO10OCT] Making Money G

洛谷那邊的題面就像一坨烤糊的司康，，在那邊提交就行了題意還是看我寫的：

小明帶著 m?塊錢走進一個山洞挖寶石，然后帶著寶石到市場去賣。

山洞里有 n?種寶石（每種寶石無限多個），第 i?種寶石的價格為 $c_i$ ，拿到寶石店能賣 $r_i$ ?塊錢。

假如小明能在市場賣掉所有采購的寶石，

求小明所獲得的最大利潤（未花完的錢算入利潤里面）的最大值。

解析：

換湯不換藥，一開始就把 r 數組轉換成利潤，之后正常完全背包。

最后從 f[m] 找到第一個 f 值不等于 f[m] 的值的前一位 p，就是真正買寶石花的錢。

輸出答案時?f[m] + m - p，因為 m - p 是未花完的錢。

#include<bits/stdc++.h>
using namespace std;const int N = 110, M = 1e5 + 10;int c[N], r[N];
int f[M];   // f 要開大點int main() {ios::sync_with_stdio(false);cin.tie(0);int n, m;cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> c[i] >> r[i];r[i] -= c[i];   //先把 r 數組轉化成利潤}memset(f, 0, sizeof(f)); for (int i = 1; i <= n; i++) if(r[i] > 0) {   //有利潤才干事for (int j = c[i]; j <= m; j++) {f[j] = max(f[j], f[j - c[i]] + r[i]);}}int p = m;while ( p > 0 && f[p] == f[p - 1]) {    //尋找真正發生“質變”的那個數，那才是真正花的錢p --;}cout << f[p] + m - p << "\n";return 0;
}

有點小巧思的例題：

P2563 [AHOI2001] 質數和分解 - 洛谷

數據范圍很小，很多種方法都可以過。

這里我就用線性篩篩出質數，然后在質數數組上完全背包。

代碼：

#include<bits/stdc++.h>
using namespace std;const int N = 310;
bool v[N];
int pr, prime[N], f[N];void init() {memset(v, 0, sizeof(v));v[1] = 1;pr = 0;for (int i = 2; i <= N - 10; i++) {if (!v[i]) {pr ++;prime[pr] = i;}for (int j = 1; j <= pr && i * prime[j] <= N - 10; j++) {int pj = prime[j];v[i * pj] = 1;if (i % pj == 0) {break;}}}
}int main() {init();int n;while (scanf("%d", &n) != EOF) {memset(f, 0, sizeof(f));f[0] = 1;for (int i = 1; i <= pr; i ++) {for (int j = prime[i]; j <= n; j ++) {f[j] += f[j - prime[i]];}}cout << f[n] << "\n";}return 0;
}

（3）多重背包

和 0/1 背包一樣，只不過這次每種物品有固定的個數。

例題 & 二進制優化：

281. 硬幣 - AcWing題庫

解析：

為了方便學校 oj 使用，我單開了一篇。

麻煩大家點這個鏈接。

例題 & 單調隊列優化：

（自行百度/oiwiki 單調隊列是什么）

P1776 寶物篩選 - 洛谷

解析：

為了方便學校 oj 使用，我又單開了一篇。

麻煩大家點這個。

背包問題的基礎就到這里啦，還有些變種問題，以后可能會講。

感謝您的閱讀。

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/web/95679.shtml
繁體地址，請注明出處：http://hk.pswp.cn/web/95679.shtml
英文地址，請注明出處：http://en.pswp.cn/web/95679.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！