背包问题是线性背包中的一类重要问题。
0/1背包
模型：
给定N个物品，每一个物品具有两种属性，一个是体积 vi ，另一个是容积 w_i 。
有一个容积为M的背包，求一种方案，使得选择的物品的体积不超过背包体积的情况下，使得获得的总价值最大。
0/1背包的时间复杂度是O(n*m)。
空间复杂度随着写法的不同而不同。
方法一：按照定义写
#include 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 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 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 4 1 1 2 2
输出样例：
3
这道题目也可以看做是0/1背包的变种。
（n个数字选择一些）
代码实现
#include 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种物品，每一种物品具有两种属性，一个是体积 v_i ，另一个是容积 w_i 。
有一个容积为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
输出样例：
14
这一种题目看起来简直不像是背包问题。。。
但是可以进行归纳：
有体积为1~n的物品以及体积为n的背包，每一个物品可以放入多次，求使得背包装满的方案数。
#include using namespace std; #define N 4010 typedef 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 2 1 2 2 3 4 1 6 2 0 0
输出样例：
Jury #1 Best jury has value 6 for prosecution and value 4 for defence: 2 3
算是比较难的一道题目。
如果使用动态规划，会发现有四个维度
- 在N个人中，已经处理了的人的数目。
- 已经选择的人的数目。
- 所有辩方与控方的差。
- 辩方以及控方法和。
（要满足差的绝对值最小的情况下，和最大）
闫氏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 using namespace std; #define N 205 #define M 25 #define P 805 const 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种物品，每一种物品具有三种属性，一个是体积 v_i ，一个是容积 w_i ，还有一个是数量num_i。
有一个容积为M的背包，求一种方案，使得选择的物品的体积不超过背包体积的情况下，使得获得的总价值最大。
这里有三种拆分方法
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)- 直接拆分。
- 二进制拆分。
- 使用优先队列进行优化。
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 5 1 2 3 2 4 1 3 4 3 4 5 2
输出样例：
10
这一道题目数据量很水，所以使用直接拆分（时间复杂度过于高！！！）
#include using namespace std; #define N 120 int 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 5 1 2 3 2 4 1 3 4 3 4 5 2
输出样例：
10
这是二进制拆分的节奏
二进制拆分太奇妙了！！！！！
如果是直接拆分，相当于是把个数拆分成一堆的1，根据这些1，可以组成任意一种数目。
但是显然没有必要。如果使用二进制拆分，那么可以根据已有的“虚拟的”物品的选择与否，组合成任意数目的等价于选择了k(k\in[1, num[i]])的这一个物品。
注意：所给定的二进制数字仅且仅仅可以表示出0~num[i]的数字
#include using namespace std; #define N 2020 int s[N], w[N], v[N]; struct QWER{ int w, v; }; vectorvec; 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≤100,
1≤M≤10^5,
1≤A_i≤10^5,
1≤C_i≤1000
输入用例：
3 10 1 2 4 2 1 1 2 5 1 4 2 1 0 0
输出用例：
8 4
虽然是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 5 2 1 2 2 4 1 3 4 1 4 5
输出样例：
8
其实也没有什么好的优化方法，直接N^3暴力进行。
#include using namespace std; #define N 105 int 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; }