专栏指路：《算法速成课》
前导：
动态规划问题中最入门、也最多变的，当属背包问题。
简单来说，就是在有限的空间，（花费最小的代价）达成最大的收益。
本文会讲一些常见的背包问题（可通过目录挑选题目），难度普及提高左右，配套一些例题。
个人认为比 oiwiki 更适合初学者一点，不过肯定没人家全。
（1）0/1 背包
有 n 个物品，每个物品的重量为 。
我们有一个最大承重为 v 的背包。
从 n 个物品中选若干个装入背包，使得所选物品的和 s 尽量接近 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 个数列。 设 为从第 i 个数列选若干个数的和。
（当然，一个数列有很多个 ）
设整数 K 满足所有数列 中都有 K，求 K 的最大值。
解析：
每个数列都搞一个 0/1 背包，如果这个数列可以达到 i 那么 sum[i]++。
最后找最大的 i 满足 sum[i] = T。
代码就不给了。
例题 2：
小明背着一个背包（最大能带的重量为 T）走进一个山洞。
山洞里有 n 个宝石，第 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 种物品，每种物品的重量为 ，有无限个。
我们有一个最大承重为 v 的背包。
从 n 种物品中选若干个装入背包，使得所选物品的和 s 尽量接近 v ，即 v - s 的值最小。
输入第 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 种宝石的价格为 ，拿到宝石店能卖
块钱。
假如小明能在市场卖掉所有采购的宝石，
求小明所获得的最大利润（未花完的钱算入利润里面）的最大值。
解析：
换汤不换药，一开始就把 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 使用，我又单开了一篇。
麻烦大家点这个。
背包问题的基础就到这里啦，还有些变种问题，以后可能会讲。
感谢您的阅读。
解析（80）)
