背包问题是线性背包中的一类重要问题。

0/1背包

模型：
给定N个物品，每一个物品具有两种属性，一个是体积 vivi ，另一个是容积 wiwi 。
有一个容积为M的背包，求一种方案，使得选择的物品的体积不超过背包体积的情况下，使得获得的总价值最大。

0/1背包的时间复杂度是O(n∗m)O(n∗m)。

空间复杂度随着写法的不同而不同。

方法一：按照定义写

#include <bits/stdc++.h>using namespace std;int n, m;//n表示的是商品的数目，m表示的是背包的容积。int f[100][100];int v[100];//第i个物品的体积int w[100];//第i个物品的价值int main(){ 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); memset(f, 0xcf, sizeof(f)); //求最优化问题时，把整体全部赋值为无穷大，这样可以防止不合法的情况对最终的判断造成干扰 f[0][0] = 0; //只需要赋值这一个就好，随着DP进行，f[i][0]全部都会是0。 //虽然f[0][i](i > 0)还是正无穷大，但是对于答案不会造成影响。 for(int i = 1; i <= n; i++) { for(int j = 0; j <= m; j++) f[i][j] = f[i-1][j];//要注意从0开始进行。 for(int j = v[i]; j <= m; j++) f[i][j] = max(f[i][j], f[i-1][j-v[i]]+w[i]); } return 0;}

方法二：采用滚动数组来进行求解。

原理：观察到更新时所使用到的信息仅仅与上一行有关系，与其他行并没有关系。

所以可以采用2*m的滚动数组。

#include <bits/stdc++.h>using namespace std;int n, m;//n表示的是商品的数目，m表示的是背包的容积。int f[2][100];int v[100];//第i个物品的体积int w[100];//第i个物品的价值int main(){ 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); memset(f, 0xcf, sizeof(f)); //求最优化问题时，把整体全部赋值为无穷大，这样可以防止不合法的情况对最终的判断造成干扰 f[0][0] = 0; //只需要赋值这一个就好，随着DP进行，f[i][0]全部都会是0。 //虽然f[0][i](i > 0)还是正无穷大，但是对于答案不会造成影响。 for(int i = 1; i <= n; i++) { for(int j = 0; j <= m; j++) f[i&1][j] = f[(i-1)&1][j];//要注意从0开始进行。 for(int j = v[i]; j <= m; j++) f[i&1][j] = max(f[i&1][j], f[(i-1)&1][j-v[i]]+w[i]); } return 0;}

总结：滚动数组可以使用位运算&来进行，这样既可以达到f数组的维护，还便于计数。

方法三：采用一维数组进行维护

条件：可以使用滚动数组进行实现，并且按照一定的扫描顺序，更新过的值不会参与到其他值的计算中。

#include <bits/stdc++.h>using namespace std;int n, m;//n表示的是商品的数目，m表示的是背包的容积。int f[100];int v[100];//第i个物品的体积int w[100];//第i个物品的价值int main(){ 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); memset(f, 0xcf, sizeof(f)); //求最优化问题时，把整体全部赋值为无穷大，这样可以防止不合法的情况对最终的判断造成干扰 f[0] = 0; for(int i = 1; i <= n; i++) { for(int j = m; j >= v[i]; j--) f[j] = max(f[j], f[j-v[i]]+w[i]); } return 0;}

AcWing278. 数字组合

给定 N 个正整数 A1,A2,…,A**N，从中选出若干个数，使它们的和为 M，求有多少种选择方案。

输入格式

第一行包含两个整数 N 和 M。

第二行包含 N 个整数，表示 A1,A2,…,A N。

输出格式

包含一个整数，表示可选方案数。

数据范围

1≤N≤100,
1≤M≤10000,
1≤A i≤1000,
答案保证在 int 范围内。

输入样例：

4 41 1 2 2

输出样例：

3

这道题目也可以看做是0/1背包的变种。
（n个数字选择一些）

#include <bits/stdc++.h>using namespace std;int f[10020];int a[102];//存储每一个数字的大小int main(){ int n, m; scanf("%d%d", &n, &m); f[0] = 1; for(int i = 1; i <= n; i++) scanf("%d", a+i); for(int i = 1; i <= n; i++) { for(int j = m; j >= a[i]; j--) f[j] += f[j-a[i]]; } printf("%d", f[m]); return 0;}

细节的考虑

现在从最一开始进行考虑：

对于f[105][10020]，全部初始化为0；

把f[0][0]初始化为1；

然后优化即可。

模型：
给定N种物品，每一种物品具有两种属性，一个是体积 vivi ，另一个是容积 wiwi 。
有一个容积为M的背包，求一种方案，使得选择的物品的体积不超过背包体积的情况下，使得获得的总价值最大。
与0/1背包不同的最大之处在于对于一种物品，可以选择无数次。

精髓：

对于完全背包，由于一个物品可以选择许多次，所以有以下方程

但是第二步骤显得过于冗杂，所以不妨优化为

上面这一个蕴含玄机：这种情况一定选择了一种以上，至于到底是多少，并不关心，反正是选择多次这一个物品，使得总价值最大。

优化：

和0/1背包一致，使用一维数组，只不过这一次是要从左向右。

int a[100];//体积int f[100];int w[100];//价值int main(){ int n, m; scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) scanf("%d", a+i); for(int i = 1; i <= n; i++) scanf("%d", w+i); memset(f, 0xcf, sizeof(f)); f[0] = 0; for(int i = 1; i <= n; i++) { for(int j = a[i]; j <= m; j++) f[j] = max(f[j], f[j-a[i]]+w[i]); } return 0;}

AcWing279. 自然数拆分

给定一个自然数 N，要求把 N 拆分成若干个正整数相加的形式，参与加法运算的数可以重复。

注意:

• 拆分方案不考虑顺序；
• 至少拆分成 2 个数的和。

求拆分的方案数 mod2147483648 的结果。

输入格式

一个自然数 N。

输出格式

输入一个整数，表示结果。

数据范围

1≤N≤4000

输入样例：

7

输出样例：

这一种题目看起来简直不像是背包问题。。。

但是可以进行归纳：

有体积为1~n的物品以及体积为n的背包，每一个物品可以放入多次，求使得背包装满的方案数。

#include <bits/stdc++.h>using namespace std;#define N 4010typedef long long ll;const ll mod = 2147483648;ll f[N];int n;int main(){ scanf("%d", &n); f[0] = 1; for(int i = 1; i <= n; i++) { for(int j = i; j <= n; j++) f[j] = (f[j-i]+f[j])%mod; } printf("%d", f[n]-1);//因为需要拆分成为两个数字，所以必须要减去一 return 0;}

AcWing280. 陪审团

在一个遥远的国家，一名嫌疑犯是否有罪需要由陪审团来决定。陪审团是由法官从公民中挑选的。

法官先随机挑选 N 个人（编号 1,2…,N）作为陪审团的候选人，然后再从这 N 个人中按照下列方法选出 M 人组成陪审团。

首先，参与诉讼的控方和辩方会给所有候选人打分，分值在 0 到 20 之间。第 i 个人的得分分别记为 p[i] 和 d[i]。为了公平起见，法官选出的 M 个人必须满足：辩方总分 D 和控方总分 P 的差的绝对值 |D−P| 最小。如果选择方法不唯一，那么再从中选择辨控双方总分之和 D+P 最大的方案。求最终的陪审团获得的辩方总分 D、控方总分 P，以及陪审团人选的编号。

注意：若陪审团的人选方案不唯一，则任意输出一组合法方案即可。

输入格式

输入包含多组测试数据。每组测试数据第一行包含两个整数 N 和 M。接下来 N 行，每行包含两个整数 p[i] 和 d[i]。每组测试数据之间隔一个空行。当输入数据 N=0，M=0 时，表示结束输入，该数据无需处理。

输出格式

对于每组数据，第一行输出 Jury #C，C 为数据编号，从 1 开始。

第二行输出 Best jury has value P for prosecution and value D for defence:，P 为控方总分，D 为辩方总分。

第三行输出按升序排列的陪审人选编号，每个编号前输出一个空格。

每组数据输出完后，输出一个空行。

数据范围

1≤N≤200,
1≤M≤20
0≤p[i],d[i]≤20

输入样例：

4 21 22 34 16 20 0

输出样例：

Jury #1Best jury has value 6 for prosecution and value 4 for defence: 2 3

算是比较难的一道题目。

如果使用动态规划，会发现有四个维度

1. 在N个人中，已经处理了的人的数目。
2. 已经选择的人的数目。
3. 所有辩方与控方的差。
4. 辩方以及控方法和。

（要满足差的绝对值最小的情况下，和最大）

闫氏DP分析法：

状态表示
f[i][j][k]，i表示考虑过人的数目，j表示选择的人的数目，k表示差值
把差值相同的视为一个类，集合的属性就是和最大的方案。
找差最小的时候可以枚举所有差的可能性。

状态转移
类似0/1背包：

• 如果不选择第i个人，那么就会有f[i][j][k] = max(f[i][j][k], f[i-1][j][k]).
• 如果选择第i个人，那么就会有f[i][j][k] = max(f[i][j][k], f[i-1][j-1][ k- ( p[i]-d[i] ) ])

因为最后需要的是方案数，所以需要进行回溯

可以使用结构体存起来，也可以使用到往回推的方式。

在这里，由于有两个维度，所以不太好压缩，
同时由于需要到着往回推算，所以也不能够压缩。

感觉这道题目就算不需要求方案数，我也要进行一下回溯。

#include <bits/stdc++.h>using namespace std;#define N 205#define M 25#define P 805const int base = 400;//使用base把负的数字映射到正的数字上int p[N], d[N];int f[N][M][P];int ans[M];int main(){ int T = 0; int n, m; while(scanf("%d%d", &n, &m), n || m) { for(int i = 1; i <= n; i++) { scanf("%d%d", p+i, d+i); } memset(f, 0xcf, sizeof(f)); f[0][0][base] = 0; //初始值应该是只有这么一种合法情况。 for(int i = 1; i <= n; i++) for(int j = 0; j <= m; j++)// ***********从0开始（这样到最后会有f[i][0][base]全部是0） //试想：有f[3][1][2+base](假设p[3]+d[3]==2),那么如果是选择了第三个人，那么退回去f[2][0][base] == 0,合法， //而对于其他的f[3][1][xx]，退回去是不合法的情况。 for(int k = 0; k < P; k++) { f[i][j][k] = f[i-1][j][k]; int tmp = k-(p[i] - d[i]); //if(tmp < 0 || tmp >= P) continue;//这一句话其实可以省略（因为根据题设条件应该是不会超过范围） if(j < 1) continue;//这一句话不可以省略。使得j==0的时候不参与第二种情况的更新。 f[i][j][k] = max(f[i][j][k], f[i-1][j-1][tmp]+p[i]+d[i]);//注意p[i]+d[i]这里是加 } int u = 0; while(f[n][m][base+u] < 0 && f[n][m][base-u] < 0) u++;//小于0，可以等于0，如果评审团给所有人的打分全部是0 if(f[n][m][base+u] > f[n][m][base-u]) u = base+u; else u = base-u; int cnt = 0; { int i = n, j = m; while(j) { if(f[i][j][u] == f[i-1][j][u]) { i--; } else { ans[++cnt] = i; u = u-(p[i] - d[i]); i--; j--; } } } int sp = 0, sd = 0; for(int i = 1; i <= cnt; i++) sp += p[ans[i]], sd += d[ans[i]]; printf("Jury #%d\n", ++T); printf("Best jury has value %d for prosecution and value %d for defence:\n", sp, sd); for(int i = cnt; i >= 1; i--) printf(" %d", ans[i]); puts("\n"); } return 0;}

多重背包是介于0/1背包以及完全背包之间的一个问题

模型：
给定N种物品，每一种物品具有三种属性，一个是体积 vivi ，一个是容积 wiwi ，还有一个是数量numinumi。
有一个容积为M的背包，求一种方案，使得选择的物品的体积不超过背包体积的情况下，使得获得的总价值最大。

这里有三种拆分方法

1. f[i][j] = max(f[i-1][j], f[i-1][j-v]+w, f[i-1][j-2v]+2w, ....f[i-1][j-sv]+sw)
2. 直接拆分。
3. 二进制拆分。
4. 使用优先队列进行优化。

AcWing4. 多重背包问题 I

有 N 种物品和一个容量是 V 的背包。第 i 种物品最多有 s**i 件，每件体积是 v**i，价值是 w**i。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。 输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。接下来有 N 行，每行三个整数 v**i,w**i,s**i，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤100

0<v**i,w**i,s**i≤100

输入样例

4 51 2 32 4 13 4 34 5 2

输出样例：

这一道题目数据量很水，所以使用直接拆分（时间复杂度过于高！！！）

#include <bits/stdc++.h>using namespace std;#define N 120int v[N], w[N], s[N];int f[N];int main(){ int n, m; scanf("%d%d", &n, &m); //memset(f, 0xcf, sizeof(f)); //f[0] = 0; //0/1背包貌似不应该初始化。。。 for(int i = 1; i <= n; i++) scanf("%d%d%d", v+i, w+i, s+i); for(int i = 1; i <= n; i++) for(int j = 1; j <= s[i]; j++)//默认有这么多。 for(int k = m; k >= v[i]; k--) { f[k] = max(f[k], f[k-v[i]]+w[i]); } printf("%d", f[m]); return 0;}

AcWing5. 多重背包问题 II

有 N 种物品和一个容量是 V 的背包。

第 i 种物品最多有 s**i 件，每件体积是 v**i，价值是 w**i。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。 输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行三个整数 v**i,w**i,s**i，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N≤1000
0<V≤2000
0<v i,w i,s i≤2000

提示：

本题考查多重背包的二进制优化方法。

输入样例

4 51 2 32 4 13 4 34 5 2

输出样例：

这是二进制拆分的节奏

二进制拆分太奇妙了！！！！！

如果是直接拆分，相当于是把个数拆分成一堆的1，根据这些1，可以组成任意一种数目。

但是显然没有必要。如果使用二进制拆分，那么可以根据已有的“虚拟的”物品的选择与否，组合成任意数目的等价于选择了k(k∈[1,num[i]])k(k∈[1,num[i]])的这一个物品。

注意：所给定的二进制数字仅且仅仅可以表示出0~num[i]的数字

#include <bits/stdc++.h>using namespace std;#define N 2020int s[N], w[N], v[N];struct QWER{ int w, v;};vector<QWER>vec;int f[N];int main(){ int n, m; scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) scanf("%d%d%d", w+i, v+i, s+i); for(int i = 1; i <= n; i++) { int t = s[i]; for(int k = 1; k <= t; k *= 2) { t -= k; vec.push_back({w[i]*k, v[i]*k}); } if(t > 0) vec.push_back({w[i]*t, v[i]*t}); } for(int i = 0; i < vec.size(); i++) { int val = vec[i].v; int wei = vec[i].w; for(int j = m; j >= wei; j--) { f[j] = max(f[j], f[j-wei]+val); } //printf("%d %d \n", val, wei); } printf("%d", f[m]); return 0;}

AcWing281. 硬币

给定 N 种硬币，其中第 i 种硬币的面值为 A i，共有 C i 个。

从中选出若干个硬币，把面值相加，若结果为 S，则称“面值 S 能被拼成”。求 1∼M 之间能被拼成的面值有多少个。

输入格式

输入包含多组测试用例。每组测试用例第一行包含两个整数 N 和 M。

第二行包含 2N 个整数，分别表示 A1,A2,…,A**N 和 C1,C2,…,C**N。

当输入用例 N=0，M=0 时，表示输入终止，且该用例无需处理。

输出格式

每组用例输出一个结果，每个结果占一行。

数据范围

1≤N≤1001≤N≤100,
1≤M≤1051≤M≤105,
1≤Ai≤1051≤Ai≤105,
1≤Ci≤10001≤Ci≤1000

输入用例：

3 101 2 4 2 1 12 51 4 2 10 0

输出用例：

84

虽然是POJ的"男人八题",但是还是可以做的。

对于这里，最朴素的做法int f[][]。
其中，f[i][j]表示：在考虑了前i个物品，体积恰好是j的所选物品的集合。
属性是：这个集合内是否有元素（是一个bool值）

对于第 i 个物品，有状态转移方程
f[i][j] = f[i-1][j] || f[i-1][j-v] || f[i-1][j-2v]...。

这一个是最朴素的转移方程，由于这一道题会卡常，所以要通过最朴素的方式寻找常数更加少的方案。

在寻找是否有一个1的时候，可以采用数组g保留与该位置最近的1距离该位置是多远。
如果距离大于s，那么不可以
如果距离小于等于s，那么可以

AcWing9. 分组背包问题

有 N 组物品和一个容量是 V 的背包。

每组物品有若干个，同一组内的物品最多只能选一个。 每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。输出最大价值。

输入格式

第一行有两个整数 N，V，用空格隔开，分别表示物品组数和背包容量。接下来有 N 组数据：

• 每组数据第一行有一个整数 S i，表示第 i 个物品组的物品数量；
• 每组数据接下来有 S i 行，每行有两个整数 v i j,w i j，用空格隔开，分别表示第 i 个物品组的第 j个物品的体积和价值；

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤100
0<S i≤100
0<v i j,w** i j≤100

输入样例

3 521 22 413 414 5

输出样例：

8

其实也没有什么好的优化方法，直接N3N3暴力进行。

#include <bits/stdc++.h>using namespace std;#define N 105int v[N], w[N];int f[N];int main(){ int n, m; scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) { int c; scanf("%d", &c); for(int j = 1; j <= c; j++) scanf("%d%d", v+j, w+j); for(int j = m; j >= 0; j--) { for(int k = 1; k <= c; k++) if(v[k] <= j) f[j] = max(f[j], f[j-v[k]]+w[k]); } } printf("%d", f[m]); return 0;}