背包模型
概述
最长上升子序列：序列DP（相邻两个被选择的有关系）
背包问题：组合DP，在全局的考虑之下最小
f[i][j]
：i 表示搞了多少，j 表示限制
集合：所有仅仅从前 i 个物品当中选择，并且总体积不超过j的选择方法的集合。
背包问题模型
01背包——万恶之源
有n个物品，每一个物品只有选择或者是不选择两种情况。
优化：可以从二维优化到一维（
[2][m]或者[m]
）
完全背包
最初的情况：（时间复杂度是
n
3
n^3
n
3
）
通过观察:（时间复杂度是
n
2
n^2
n
2
）
优化：可以从二维优化到一维（
[2][m]或者[m]
）
多重背包
多重背包是介于0/1背包以及完全背包之间的一个问题
给定N种物品，每一种物品具有三种属性，一个是体积
v
i
v_i
v
i
，一个是容积
w
i
w_i
w
i
，还有一个是数量
n
u
m
i
num_i
n
u
m
i
。
有一个容积为M的背包，求一种方案，使得选择的物品的体积不超过背包体积的情况下，使得获得的总价值最大。
-
直接拆分。
暴力 - 二进制拆分。
- 使用优先队列进行优化。
二进制拆分
二进制拆分太奇妙了！！！！！
如果是直接拆分，相当于是把个数拆分成一堆的1，根据这些1，可以组成任意一种数目。
但是显然没有必要。如果使用二进制拆分，那么可以根据已有的“虚拟的”物品的选择与否，组合成任意数目的等价于选择了
k(
k
∈
[
1
,
n
u
m
[
i
]
]
)
k(k\in[1, num[i]])
k
(
k
∈
[
1
,
n
u
m
[
i
]])
的这一个物品。注意：所给定的二进制数字仅且仅仅可以表示出
0~num[i]
的数字
5. 多重背包问题 II
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N≤1000
0<V≤2000
0<vi,wi,si≤2000
提示：
本题考查多重背包的二进制优化方法。
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例：
10
#include <bits/stdc++.h>
using namespace std;
#define N 2022
int v[N], w[N], s[N];
struct GOOD{
int w, v;
};
vector<GOOD> good;
int f[N];
int n ,V;
int main()
{
scanf("%d%d", &n, &V);
for(int i =1; i <= n; i++){
scanf("%d%d%d", v+i, w+i, s+i);
}
for(int i = 1; i <= n; i++)
{
int t = s[i];
for(int j = 1; j <= t; j *= 2){
t -= j;
good.push_back({w[i] * j, v[i] * j});
}
if(t > 0){
good.push_back({w[i] * t, v[i] * t});
}
}
for(int i = 0; i < good.size(); i++)
{
for(int j = V; j >= good[i].v; j--){
f[j] = max(f[j], f[j - good[i].v] + good[i].w);
}
}
printf("%d\n", f[V]);
return 0;
}
6. 多重背包问题 III
有
N
种物品和一个容量是
V
的背包。
第
i
种物品最多有
s
i 件，每件体积是
v
i，价值是
w
i。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
输入格式
第一行两个整数，
N
，
V
(
0
<
N
≤
1000,
0
<
V
≤
20000
)，用空格隔开，分别表示物品种数和背包容积。
接下来有
N
行，每行三个整数
v
i**,
w
i**,
s
i，用空格隔开，分别表示第
i
种物品的体积、价值和数量。
输出格式
输出一个整数，表示最大价值。
数据范围
0
<
N
≤
1000
0**<
V
≤
20000
0
<
v
i**,
w
i**,
s
i
≤
20000**
提示
本题考查多重背包的单调队列优化方法。
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例：
10
|
难度： 困难 |
|---|
| 时/空限制：1s / 128MB |
| 总通过数：18526 |
| 总尝试数：40062 |
| 来源：背包九讲 |
|
算法标签 |
#include <bits/stdc++.h>
using namespace std;
#define N 20020
int w[N], v[N], s[N];
int n, V;
int f[N], g[N], q[N];
int main()
{
scanf("%d%d", &n, &V);
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 <= V; j++) g[j] = f[j];
for(int r = 0; r < v[i]; r++){
int hh = 0, tt = -1;
for(int k = r; k <= V; k += v[i])
{
while(hh <= tt && q[hh] < k - s[i] * v[i]) hh ++;;
if(hh <= tt) f[k] = max(f[k], g[q[hh]] + (k - q[hh]) / v[i] * w[i]);
while(hh <= tt && g[q[tt]] + (k - q[tt]) / v[i] * w[i] <= g[k]) tt--;
q[++tt] = k;
}
}
}
printf("%d\n", f[V]);
return 0;
}
二维费用背包问题
就是费用占据两维度，仅此而已
#include <bits/stdc++.h>
using namespace std;
int n, V, M;
int f[105][105];
int main()
{
scanf("%d%d%d", &n, &V, &M);
for(int i = 1; i <= n; i++){
int v, m, w;
scanf("%d%d%d", &v, &m, &w);
for(int j = V; j >= v; j--)
{
for(int k = M; k >= m; k--){
f[j][k] = max(f[j][k], f[j - v][k - m] + w);
}
}
}
printf("%d", f[V][M]);
return 0;
}
1020. 潜水员（翻转背包）
潜水员为了潜水要使用特殊的装备。
他有一个带2种气体的气缸：一个为氧气，一个为氮气。
让潜水员下潜的深度需要各种数量的氧和氮。
潜水员有一定数量的气缸。
每个气缸都有重量和气体容量。
潜水员为了完成他的工作需要特定数量的氧和氮。
他完成工作所需气缸的总重的最低限度的是多少？
例如：潜水员有5个气缸。每行三个数字为：氧，氮的（升）量和气缸的重量：
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119
如果潜水员需要5升的氧和60升的氮则总重最小为249（1，2或者4，5号气缸）。
你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。
输入格式
第一行有2个整数
m
，
n
。它们表示氧，氮各自需要的量。
第二行为整数
k
表示气缸的个数。
此后的
k
行，每行包括
a
i，
b
i，
c
i，3个整数。这些各自是：第
i
个气缸里的氧和氮的容量及气缸重量。
输出格式
仅一行包含一个整数，为潜水员完成工作所需的气缸的重量总和的最低值。
数据范围
输入样例：
5 60
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119
输出样例：
249
题解
由于与之前的情况不太一样，重新进行分析，避免出现纰漏。
y式状态分析法：
状态表示：
f[i][j][k]
表示从前 i 个物品里面选择，氧气含量最少为 j ，氮气含量最少为 k 的所有集合。
属性：（气罐重量）最小值
状态转移：
设第i个罐子 氧气 a，氮气 b，重量c。
那么显然有
f[i][j][k] = f[i-1][j-a][k-b] + c
现在讨论4种情况：
-
当
j−
a
j-a
j
−
a
以及
k−
b
k -b
k
−
b
都大于等于0，那么正常进行 -
当
j−
a
j-a
j
−
a
大于等于0，
k−
b
k -b
k
−
b
小于0，那么对于去掉第 i 个罐子之后的剩下的罐子，对于氮气的贡献没有任何要求，但是对于氧气，还是有要求。所以等价于
f[i-1][j-a][0]
-
当
j−
a
j-a
j
−
a
小于0，
k−
b
k -b
k
−
b
大于等于0，与上一个类似 -
当
j−
a
j-a
j
−
a
以及
k−
b
k -b
k
−
b
都小于0，那么对于二者都没有要求，等价于
f[0][0]
。
在这里也要注意循环次序。
#include <bits/stdc++.h>
using namespace std;
#define N 85
#define M 25
int f[M][N];
int m, n, k;
int main()
{
scanf("%d%d%d", &m, &n, &k);
for(int i = 0; i <= m; i++){
for(int j = 0; j <= n; j++)
f[i][j] = 0x3f3f3f3f;
}
f[0][0] = 0;//
for(int i = 1; i <= k; i++)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
for(int j = m; j >= 0; j--){// 一定要从零开始，因为后面的状态还以来于 0
for(int k = n; k >= 0; k--){
f[j][k] = min(f[j][k], f[max(j-a, 0)][max(k-b, 0)] + c);
}
}
}
printf("%d", f[m][n] );
return 0;
}
12. 背包问题求具体方案
有 N件物品和一个容量是 V的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出 字典序最小的方案。这里的字典序是指：所选物品的编号所构成的序列。物品的编号范围是 1…N。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一行，包含若干个用空格隔开的整数，表示最优解中所选物品的编号序列，且该编号序列的字典序最小。
物品编号范围是 1…N。
数据范围
0<N,V≤1000
0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 6
输出样例：
1 4
- 首先，按照字典序输出并没有增加难度，我们仅仅使用贪心法就可以（从前面的物品往后贪心）
- 然后，我们从后往前推
-
需要注意：由于贪心需要从第一个物品开始，所以dp的时候从后往前DP
#include <bits/stdc++.h>
using namespace std;
#define N 1020
int f[N][N];
int v[N], w[N];
stack<int> st;
int main()
{
int n, V;
scanf("%d%d", &n, &V);
for(int i = 1; i<= n; i++){
scanf("%d%d", v+i, w+i);
}
for(int i = n; i >= 1; i--)
{
for(int j = 0; j <= V; j++){
f[i][j] = f[i+1][j];
if(j >= v[i]) f[i][j] = max(f[i][j], f[i+1][j - v[i]] + w[i]);
}
}
int k = V;
for(int i = 1; i <= n; i++){
if(k < v[i]) continue;
if(f[i+1][k]>f[i+1][k-v[i]]+w[i]){
continue;
}
else{
st.push(i);
k = k-v[i];
}
}
while(st.size())
{
printf("%d ", st.top());
st.pop();
}
return 0;
}
分组背包
定义：有不同的组，每一组有
s[i]
个物品，每一组最多可以选择1个物品。问如何选择可以在总量不超的情况下得到的价值最大
精髓：
f[i][j]
表示从前 i 组物品中选择，体积最大为 j 的时候得到的最大价值
BUG总结：注意一定不要忘记
if(j >= v[k])
语句
for 组数
for 体积
for 决策（选择这一组内那一种物品）
#include <bits/stdc++.h>
using namespace std;
#define N 150
int f[N];
int w[N], v[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(j >= v[k])f[j] = max(f[j], f[j - v[k]] + w[k]);
}
}
}
printf("%d", f[m]);
return 0;
}
7. 混合背包问题
有
N
种物品和一个容量是
V
的背包。
物品一共有三类：
- 第一类物品只能用1次（01背包）；
- 第二类物品可以用无限次（完全背包）；
-
第三类物品最多只能用
s
i 次（多重背包）；
每种体积是
v
i，价值是
w
i。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。
- si=−1 表示第 i 种物品只能用1次；
- si=0 表示第 i 种物品可以用无限次；
- si>0 表示第 i 种物品可以使用 si 次；
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
−1≤si≤1000
输入样例
4 5
1 2 -1
2 4 1
3 4 0
4 5 2
输出样例：
8
这一道题目简直就是一道大杂烩
但是为什么可以大杂烩呢？
状态表示为
f[i][j]
，对于三种背包都是相同的。
每一次转态的转移仅仅与当前的背包的类型是有关系的，与之前的东西的类型没有关系
so（都可以套）
#include <bits/stdc++.h>
using namespace std;
int n, m;
#define N 1020
int f[N];
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i<= n; i++)
{
int v, w, s;
scanf("%d%d%d", &v, &w, &s);
if(!s){
for(int j = v; j <= m; j++) f[j] = max(f[j], f[j-v] + w);
}
else{
if(s == -1) s = 1;
int t = s;
for(int k = 1; k <= t; k *= 2){
for(int j = m; j >= v * k; j--){
f[j] = max(f[j], f[j - v * k] + w * k);
}
t -= k;
}
if(t > 0){
for(int j = m; j >= v * t; j--){
f[j] = max(f[j], f[j - t * v] + w * t);
}
}
}
}
printf("%d", f[m]);
return 0;
}
11. 01背包问题求最优方案数
有
N
件物品和一个容量是
V
的背包。每件物品只能使用一次。
第
i
件物品的体积是
v
i，价值是
w
i�。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出
最优选法的方案数
。注意答案可能很大，请输出答案模
10
9**+**7 的结果。
输入格式
第一行两个整数，
N
，
V
，用空格隔开，分别表示物品数量和背包容积。
接下来有
N
行，每行两个整数
v
i**,
w
i**，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数，表示
方案数
模
10
9**+**7 的结果。
数据范围
0
<
N
,
V
≤
1000
0**<
v
i**,
w
i
≤
1000
输入样例
4 5
1 2
2 4
3 4
4 6
输出样例：
2
题解
-
类似于图论中利用拓扑排序求最短路的条数一样，如果可以存哪一个转移过去，那么就
g[y] += g[x]
- 这里的状态表示与01背包是一致的
- 可以压缩到一维（当前维数仅仅与上一维有关系，并且体积从大到小循环可以行得通）
-
初始值
g[i]
应该为1.
#include <bits/stdc++.h>
using namespace std;
int n, m;
#define M 1005
long long f[M], g[M];
const long long mod = 1e9+7;
int main()
{
scanf("%d%d", &n, &m);
for(int i = 0; i <= m; i++) g[i] = 1;
for(int i = 1; i <= n; i++)
{
long long v, w;
scanf("%lld%lld", &v, &w);
for(int j = m; j >= v; j--){
if(f[j] == f[j - v] + w){
g[j] = (g[j] + g[j - v]) %mod;
}
else if(f[j] > f[j - v] +w){
g[j] = g[j];
}
else
{
g[j] = g[j - v];
f[j] = f[j - v] + w;
}
}
}
printf("%lld", g[m]);
return 0;
}
背包问题的应用
1022. 宠物小精灵之收服
（01背包）
宠物小精灵是一部讲述小智和他的搭档皮卡丘一起冒险的故事。
一天，小智和皮卡丘来到了小精灵狩猎场，里面有很多珍贵的野生宠物小精灵。
小智也想收服其中的一些小精灵。
然而，野生的小精灵并不那么容易被收服。
对于每一个野生小精灵而言，小智可能需要使用很多个精灵球才能收服它，而在收服过程中，野生小精灵也会对皮卡丘造成一定的伤害（从而减少皮卡丘的体力）。
当皮卡丘的体力小于等于0时，小智就必须结束狩猎（因为他需要给皮卡丘疗伤），而使得皮卡丘体力小于等于0的野生小精灵也不会被小智收服。
当小智的精灵球用完时，狩猎也宣告结束。
我们假设小智遇到野生小精灵时有两个选择：收服它，或者离开它。
如果小智选择了收服，那么一定会扔出能够收服该小精灵的精灵球，而皮卡丘也一定会受到相应的伤害；如果选择离开它，那么小智不会损失精灵球，皮卡丘也不会损失体力。
小智的目标有两个：主要目标是收服尽可能多的野生小精灵；如果可以收服的小精灵数量一样，小智希望皮卡丘受到的伤害越小（剩余体力越大），因为他们还要继续冒险。
现在已知小智的精灵球数量和皮卡丘的初始体力，已知每一个小精灵需要的用于收服的精灵球数目和它在被收服过程中会对皮卡丘造成的伤害数目。
请问，小智该如何选择收服哪些小精灵以达到他的目标呢？
输入格式
输入数据的第一行包含三个整数：N，M，K，分别代表小智的精灵球数量、皮卡丘初始的体力值、野生小精灵的数量。
之后的K行，每一行代表一个野生小精灵，包括两个整数：收服该小精灵需要的精灵球的数量，以及收服过程中对皮卡丘造成的伤害。
输出格式
输出为一行，包含两个整数：C，R，分别表示最多收服C个小精灵，以及收服C个小精灵时皮卡丘的剩余体力值最多为R。
数据范围
0<N≤1000,
0<M≤500,
0<K≤100
输入样例1：
10 100 5
7 10
2 40
2 50
1 20
4 20
输出样例1：
3 30
输入样例2：
10 100 5
8 110
12 10
20 10
5 200
1 110
输出样例2：
0 100
题解
这里我使用二维费用背包
背包的费用可以有两个，最优值显然是收获小精灵的个数，但是同时还有次要求条件（皮卡丘的体力值最大，其实最后扫一遍就可以了）
#include <bits/stdc++.h>
using namespace std;
int f[1003][502];
int V1, V2, n;
int main()
{
scanf("%d%d%d", &V1, &V2, &n);
for(int i = 1; i <= n; i++)
{
int v1, v2;
scanf("%d%d", &v1, &v2);
for(int j = V1; j >= v1; j--)
{
for(int k = V2 - 1; k >= v2; k--){
f[j][k] = max(f[j][k], f[j - v1][k - v2] + 1);// 注意皮卡丘的体力不可以为0
// 所以相当于容量是V2 - 1
}
}
}
int maxv = f[V1][V2 - 1];
int k = V2 - 1;
while(k >0 && f[V1][k - 1] == maxv) k--;// 注意k >0的边界限制
cout << f[V1][V2 - 1] << " " << V2 - k;
return 0;
}
278. 数字组合
给定 N 个正整数 A1,A2,…,从中选出若干个数，使它们的和为 M，求有多少种选择方案。
输入格式
第一行包含两个整数 N 和 M。
第二行包含 N 个整数，表示 A1,A2,…,AN
输出格式
包含一个整数，表示可选方案数。
数据范围
1≤N≤100
1
≤
M
≤
10000
1≤Ai≤1000
答案保证在 int 范围内。
输入样例：
4 4
1 1 2 2
输出样例：
3
#include <bits/stdc++.h>
using namespace std;
#define N 10020
int n, m;
int a[N];
int main()
{
scanf("%d%d", &n, &m);
a[0] = 1;
for(int i =1; i <= n; i++)
{
int x;
scanf("%d", &x);
for(int j = m; j >= x; j--){
a[j] += a[j-x];
}
}
printf("%d", a[m]);
return 0;
}
1023. 买书
小明手里有n元钱全部用来买书，书的价格为10元，20元，50元，100元。
问小明有多少种买书方案？（每种书可购买多本）
输入格式
一个整数 n，代表总共钱数。
输出格式
一个整数，代表选择方案种数。
数据范围
0
≤
n
≤
1000
输入样例1：
20
输出样例1：
2
输入样例2：
15
输出样例2：
0
输入样例3：
0
输出样例3：
1
题解
这个是计数类的完全背包。为了保险起见，我浅浅推一下
f
[
i
]
[
j
]
=
f
[
i
−
1
]
[
j
]
+
f
[
i
−
1
]
[
j
−
1
p
]
+
f
[
i
−
1
]
[
j
−
2
p
]
+
⋅
⋅
⋅
⋅
+
f
[
i
−
1
]
[
j
−
s
p
]
f
[
i
]
[
j
−
p
]
=
f
[
i
−
1
]
[
j
−
1
p
]
+
f
[
i
−
1
]
[
j
−
2
p
]
+
⋅
⋅
⋅
⋅
+
f
[
i
−
1
]
[
j
−
s
p
]
f[i][j] = f[i-1][j]+f[i-1][j-1p]+f[i-1][j-2p]+····+f[i-1][j-sp] \\ f[i][j-p] =f[i-1][j-1p]+f[i-1][j-2p]+····+f[i-1][j-sp]
f
[
i
]
[
j
]
=
f
[
i
−
1
]
[
j
]
+
f
[
i
−
1
]
[
j
−
1
p
]
+
f
[
i
−
1
]
[
j
−
2
p
]
+
⋅⋅⋅⋅
+
f
[
i
−
1
]
[
j
−
s
p
]
f
[
i
]
[
j
−
p
]
=
f
[
i
−
1
]
[
j
−
1
p
]
+
f
[
i
−
1
]
[
j
−
2
p
]
+
⋅⋅⋅⋅
+
f
[
i
−
1
]
[
j
−
s
p
]
经坚定为
f[i][j] += f[i][j-p]
代码
#include <bits/stdc++.h>
using namespace std;
#define N 1002
int f[N];
int main()
{
int p[4] = {10, 20, 50, 100};
f[0] = 1;
int m;
scanf("%d", &m);
for(int i = 0; i < 4; i++)
{
for(int j = p[i]; j <= m; j++) f[j] += f[j - p[i]];
}
printf("%d", f[m]);
return 0;
}
注意计数类DP中，
f[0]
搞成1
1013. 机器分配
总公司拥有
M
台
相同
的高效设备，准备分给下属的
N
个分公司。
各分公司若获得这些设备，可以为国家提供一定的盈利。盈利与分配的设备数量有关。
问：如何分配这M台设备才能使国家得到的盈利最大？
求出最大盈利值。
分配原则：每个公司有权获得任意数目的设备，但总台数不超过设备数
M
。
输入格式
第一行有两个数，第一个数是分公司数
N
，第二个数是设备台数
M
；
接下来是一个
N
×
M
的矩阵，矩阵中的第
i
行第
j
列的整数表示第
i
个公司分配
j
台机器时的盈利。
输出格式
第一行输出最大盈利值；
接下
N
行，每行有
2
个数，即分公司编号和该分公司获得设备台数。
答案不唯一，输出任意合法方案即可。
数据范围
1≤N≤10,
1
≤
M
≤
15
输入样例：
3 3
30 40 50
20 30 50
20 25 30
输出样例：
70
1 1
2 1
3 1
题解
对于每一个公司，由于随着设备的分配没有明显的关系，所以不可以简单套用01背包进行求解。但是我们可以把公司看成组。把选择1个机器，两个机器，三个机器看成是不同的物品。每一个公司选择一种情况。
但是难点就在于如何表述状态
也就是遍历所有的决策，找到一个转移过去的就可以了。
**拓展：**如果要求字典序最小，那么就可以在DP的时候反着D
#include <bits/stdc++.h>
using namespace std;
#define N 21
int w[N][N];
int f[N][N];
int n, m;
int ans[N];
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++){
scanf("%d", &w[i][j]);
}
for(int i = 1; i <= n; i++){
for(int j = m; j >= 0; j--){
f[i][j] = f[i-1][j];
for(int k = 0; k <= j; k++){//k必须大于等于j
f[i][j] = max(f[i][j], f[i-1][j - k]+w[i][k]);
}
}
}
int k = m;
for(int i = n; i; i--)
{
for(int j = 0; j <= k; j++){
if(f[i][k] == f[i-1][k - j]+w[i][j] ) {
ans[i] = j;
k -= j;
break;
}
}
}
printf("%d\n", f[n][m]);
for(int i = 1; i<= n; i++) printf("%d %d\n", i, ans[i]);
return 0;
}
487. 金明的预算方案
金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。
更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。
今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：
如果要买归类为附件的物品，必须先买该附件所属的主件。
每个主件可以有0个、1个或2个附件。
附件不再有从属于自己的附件。
金明想买的东西很多，肯定会超过妈妈限定的N元。
于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。
他还从因特网上查到了每件物品的价格（都是10元的整数倍）。
他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j1，j2，…，jk，则所求的总和为：
v[j1]∗w[j1]+v[j2]∗w[j2]+…+v[jk]∗w[jk]（其中*为乘号）
请你帮助金明设计一个满足要求的购物单。
输入格式
输入文件的第1行，为两个正整数，用一个空格隔开：N m，其中N表示总钱数，m为希望购买物品的个数。
从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有3个非负整数v p q，其中v表示该物品的价格，p表示该物品的重要度（1~5），q表示该物品是主件还是附件。
如果q=0，表示该物品为主件，如果q>0，表示该物品为附件，q是所属主件的编号。
输出格式
输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<200000）。
数据范围
N<32000,m<60,v<10000
输入样例：
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
输出样例：
2200
题解
这里面的主件以及附件是有依赖的，所以不能直接套用01背包问题。
但是对于不相同的主件，选择以及不选择是相互独立的，所以可以套用01背包。
在每一个主件（可能包含附件）内部，暴力枚举所有的互斥的情况，视为
分组背包
感觉分组背包就是一部分暴力，另一部分套用01背包。
如果
不要脸
的话，我可以视为有一组，然后把所有的情况全部枚举一遍，当成这一组内部的物品。。。。
不要忽视：每一个主件最多仅仅有2个附件，所以可以进行枚举
#include <bits/stdc++.h>
using namespace std;
#define M 32060
#define N 70
struct Node{
int v, w;
};
Node master[N];
vector<Node> ser[N];
int n, m;
int f[M];
int main()
{
scanf("%d%d", &m, &n);
for(int i = 1; i <= n; i++){
int v, p, q;
scanf("%d%d%d", &v, &p, &q);
if(q == 0) master[i] = {v, p * v};
else ser[q].push_back({v, p * v});
}
for(int i = 1; i <= n; i++)
{
if(!master[i].w && !master[i].v) continue;
for(int j = m; j >= 0; j--)
{
for(int k = 0; k < (1 << ser[i].size()); k++)
{
int v = master[i].v, w = master[i].w;
for(int u = 0; u < ser[i].size(); u++){
if(1&(k >> u)){
v += ser[i][u].v;
w += ser[i][u].w;
}
}
if(j >= v){
f[j] = max(f[j], f[j-v] + w);
}
}
}
}
printf("%d", f[m]);
return 0;
}
532. 货币系统
在网友的国度中共有
n
种不同面额的货币，第
i
种货币的面额为
a
[
i
]，你可以假设每一种货币都有无穷多张。
为了方便，我们把货币种数为
n
、面额数组为
a
[
1…
n
]
的货币系统记作
(
n
,
a
)
。
在一个完善的货币系统中，每一个非负整数的金额
x
都应该可以被表示出，即对每一个非负整数
x
，都存在
n
个非负整数
t
[
i
] 满足
a
[
i
]
×
t**[
i
]** 的和为
x
。
然而，在网友的国度中，货币系统可能是不完善的，即可能存在金额
x
不能被该货币系统表示出。
例如在货币系统 n=3, a=[2,5,9]中，金额 1,3 就无法被表示出来。
两个货币系统
(
n
,
a
)
和
(
m
,
b
)
是等价的，当且仅当对于任意非负整数
x
，它要么均可以被两个货币系统表出，要么不能被其中任何一个表出。
现在网友们打算简化一下货币系统。
他们希望找到一个货币系统
(
m
,
b
)
，满足 **(
m
,
b
)**与原来的货币系统 **(
n
,
a
)**等价，且
m
尽可能的小。
他们希望你来协助完成这个艰巨的任务：找到最小的
m
。
输入格式
输入文件的第一行包含一个整数
T
，表示数据的组数。
接下来按照如下格式分别给出
T
组数据。
每组数据的第一行包含一个正整数
n
。
接下来一行包含
n
个由空格隔开的正整数
a
[
i
]。
输出格式
输出文件共有
T
行，对于每组数据，输出一行一个正整数，表示所有与
(
n
,
a
)
等价的货币系统
(
m
,
b
)
中，最小的
m
。
数据范围
1
≤
n
≤
100
,
1
≤
a**[
i
]
≤
25000**,
1
≤
T
≤
20
输入样例：
2
4
3 19 10 6
5
11 29 13 19 17
输出样例：
2
5
题解
这里是求解线性代数问题。
首先有一点性质：
- 寻找到的最优解{b1, b2, …}中，所有的数字一定全部属于{a1, a2, a3 …}
证明：
假设存在bk不属于原始的集合，那么由于最优的集合以及原始的集合所能表示的范围是相同的。所以bk可以通过原来的集合表示出来bk=a1+a3+…，原来的集合又可以使用b中的数字表示。所以最终bk可以通过b中的比bk小的数字进行表示，所以bk并没有必要。
通过这一个性质，我们就可以通过在a中删除一些元素来得到b，而无需凭空的构造。
然后面对a，如果某一个数字可以被其他数字表示出来，那么一定不会出现在b中。
反之，则一定出现在b中。
#include <bits/stdc++.h>
using namespace std;
#define N 25020
int f[N];
int a[120];
int main()
{
int T;
cin >> T;
while(T--)
{
int ans = 0;
int n;
scanf("%d", &n);
for(int i = 1; i<= n; i++){
scanf("%d", a+i);
}
sort(a+1, a+n+1);// sort的妙用
for(int i = 0; i <= a[n]; i++) f[i] = 0;
f[0] = 1;
for(int i = 1; i<= n; i++){
if(f[a[i]]) continue;
ans ++;
for(int j = a[i]; j <= a[n]; j++){
f[j] = max(f[j], f[j - a[i]]);
}
}
printf("%d\n", ans);
}
return 0;
}
sort鉴赏：
根据上面所推倒出的性质，需要检查每一个
a[i]
，如果不能被其他的表示，那么b里面有这一个
a[i]
但是如果可以被其他的表示，那么这个
a[i]
就是多余的。
如果要是暴力枚举的话，时间复杂度是
N
2
M
N^2M
N
2
M
，这样时间复杂度一定会炸。
现在我们来考虑，如果比
a[i]
小的数字不能表示，那么就相当于不能表示。
所以可以进行一下排序。
对于当前的
a[i]
，如果不能表示，那么就是不能表示（比他小的不能表示他）
然后把
a[i]
应用一下完全背包。
10. 有依赖的背包问题
有 N 个物品和一个容量是 V 的背包。
物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。
如下图所示：
如果选择物品5，则必须选择物品1和2。这是因为2是5的父节点，1是2的父节点。
每件物品的编号是 i，体积是 vi，价值是 wi，依赖的父节点编号是 pi。物品的下标范围是 1…N。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行有两个整数 N，V，用空格隔开，分别表示物品个数和背包容量。
接下来有 N 行数据，每行数据表示一个物品。
第 i 行有三个整数 vi,wi,pi，用空格隔开，分别表示物品的体积、价值和依赖的物品编号。
如果 pi=−1，表示根节点。 数据保证所有物品构成一棵树。
输出格式
输出一个整数，表示最大价值。
数据范围
1≤N,V≤100
1≤vi,wi≤100
父节点编号范围：
- 内部结点：1≤pi≤N;
- 根节点 pi=−1;
输入样例
5 7
2 3 -1
2 2 1
3 5 1
4 7 2
3 6 2
输出样例：
11
题解
这一道题目与金明的预算都是有依赖的背包。
但是由于金明的预算中，枚举依赖背包的方案最多才有 4 种情况，所以就进行暴力枚举。（把不同的方案归为一组，在这一组中选择出一个）
但是在这道题目中，如果暴力枚举，必超时，所以可以枚举体积（每一个体积下子树有一个最大价值，把这个看成物品（这个体积）的价值，然后归为一类，从里面选择一个）
#include <bits/stdc++.h>
using namespace std;
int n, m;
#define N 105
int head[N], ver[N], nxt[N], tot;// 建立的是单向边
inline void add(int x, int y){
ver[++tot] = y;
nxt[tot] = head[x];
head[x] = tot;
}
int root;
int v[N], w[N];
int f[N][N];
void dfs(int x)
{
for(int i = v[x]; i <= m; i++) f[x][i] = w[x];
for(int i = head[x]; i; i = nxt[i])
{
int y = ver[i];
dfs(y);
for(int j = m; j >= v[x]; j--){
for(int k = 0; k <= j - v[x]; k++){
f[x][j] = max(f[x][j], f[y][k] + f[x][j - k]);
}
}
}
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++)
{
int v1, w1, p;
scanf("%d%d%d", &v1, &w1, &p);
v[i] = v1;
w[i] = w1;
if(p == -1) root = i;
else{
add(p, i);
}
}
dfs(root);
printf("%d", f[root][m]);
return 0;
}