特征：每种物品只有一个，可以选择放置或不放置
状态转移方程如下：
当
v
≥
w
i
vge w_i
v≥wi时：
d
p
[
i
]
[
v
]
=
m
a
x
(
d
p
[
i
−
1
]
[
v
]
,
d
p
[
i
−
1
]
[
v
−
w
i
]
+
c
i
)
dp[i][v]=max(dp[i-1][v],dp[i-1][v-w_i]+c_i)
dp[i][v]=max(dp[i−1][v],dp[i−1][v−wi]+ci)
当
v
<
w
i
v< w_i
v
时间复杂度： O ( N V ) O(NV) O(NV)，空间复杂度： O ( N V ) O(NV) O(NV)
可以发现，我们可以将状态压缩到一维，空间复杂度降低至
O
(
V
)
O(V)
O(V)
注意，
d
p
dp
dp 过程中，本层次的
v
v
v 是由上层次更小的
v
v
v 转移过来，所以要逆序遍历，而当
v
<
w
i
v
易错点提示：要注意看背包要不要求装满！
若要求最后背包必须装满，则初始化时：
d
p
[
0
]
=
0
,
d
p
[
1..
V
]
=
−
∞
dp[0]=0, dp[1..V]=-infty
dp[0]=0, dp[1..V]=−∞
若不要求：
d
p
[
0...
V
]
=
0
dp[0...V]=0
dp[0...V]=0
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
输入格式第一行有 2 2 2 个整数 T T T（ 1 ≤ T ≤ 1000 1 le T le 1000 1≤T≤1000）和 M M M（ 1 ≤ M ≤ 100 1 le M le 100 1≤M≤100），用一个空格隔开， T T T 代表总共能够用来采药的时间， M M M 代表山洞里的草药的数目。
接下来的 M M M 行每行包括两个在 1 1 1 到 100 100 100 之间（包括 1 1 1 和 100 100 100）的整数，分别表示采摘某株草药的时间和这株草药的价值。
输出格式输出在规定的时间内可以采到的草药的最大总价值。
样例 #1 样例输入 #170 3 71 100 69 1 1 2样例输出 #1
3提示
【数据范围】
- 对于 30 % 30% 30% 的数据， M ≤ 10 M le 10 M≤10；
- 对于全部的数据， M ≤ 100 M le 100 M≤100。
【题目来源】
NOIP 2005 普及组第三题
#include例2 [AcWing 1022] 宠物小精灵之收服#include #include #include #include #include #include #include #include
宠物小精灵是一部讲述小智和他的搭档皮卡丘一起冒险的故事。
一天，小智和皮卡丘来到了小精灵狩猎场，里面有很多珍贵的野生宠物小精灵。
小智也想收服其中的一些小精灵。
然而，野生的小精灵并不那么容易被收服。
对于每一个野生小精灵而言，小智可能需要使用很多个精灵球才能收服它，而在收服过程中，野生小精灵也会对皮卡丘造成一定的伤害（从而减少皮卡丘的体力）。
当皮卡丘的体力小于等于0时，小智就必须结束狩猎（因为他需要给皮卡丘疗伤），而使得皮卡丘体力小于等于0的野生小精灵也不会被小智收服。
当小智的精灵球用完时，狩猎也宣告结束。
我们假设小智遇到野生小精灵时有两个选择：收服它，或者离开它。
如果小智选择了收服，那么一定会扔出能够收服该小精灵的精灵球，而皮卡丘也一定会受到相应的伤害；如果选择离开它，那么小智不会损失精灵球，皮卡丘也不会损失体力。
小智的目标有两个：主要目标是收服尽可能多的野生小精灵；如果可以收服的小精灵数量一样，小智希望皮卡丘受到的伤害越小（剩余体力越大），因为他们还要继续冒险。
现在已知小智的精灵球数量和皮卡丘的初始体力，已知每一个小精灵需要的用于收服的精灵球数目和它在被收服过程中会对皮卡丘造成的伤害数目。
请问，小智该如何选择收服哪些小精灵以达到他的目标呢？
输入格式
输入数据的第一行包含三个整数：
N
N
N，
M
M
M，
K
K
K，分别代表小智的精灵球数量、皮卡丘初始的体力值、野生小精灵的数量。
之后的K行，每一行代表一个野生小精灵，包括两个整数：收服该小精灵需要的精灵球的数量，以及收服过程中对皮卡丘造成的伤害。
输出格式
输出为一行，包含两个整数：
C
C
C，
R
R
R，分别表示最多收服
C
C
C个小精灵，以及收服
C
C
C个小精灵时皮卡丘的剩余体力值最多为
R
R
R。
数据范围 本题是典型的二维费用的0-1背包问题，即两个体积元素：精灵球的数量和给皮卡丘造成的伤害，目标函数是：收服的精灵尽可能地多，精灵相同的同时皮卡丘的伤害总和最小。。。思路是直接dp，最后在精灵数量相同的里面找伤害值最小的。。（注意皮卡丘的生命值不能为0） 背包dp中价值与体积的互逆性题解链接 给定
N
N
N 个正整数
A
1
,
A
2
,
…
,
A
N
A_1,A_2,…,A_N
A1,A2,…,AN，从中选出若干个数，使它们的和为
M
M
M，求有多少种选择方案。 输入格式 第二行包含
N
N
N 个整数，表示
A
1
,
A
2
,
…
,
A
N
A_1,A_2,…,A_N
A1,A2,…,AN。 输出格式 数据范围 本题是计数类的背包
d
p
dp
dp 问题，状态转移方程是：
d
p
[
i
]
[
v
]
=
d
p
[
i
−
1
]
[
v
]
+
d
p
[
i
−
1
]
[
v
−
w
i
]
dp[i][v]=dp[i-1][v]+dp[i-1][v-w_i]
dp[i][v]=dp[i−1][v]+dp[i−1][v−wi] 有
N
N
N 件物品和一个容量是
V
V
V 的背包。每件物品只能使用一次。 第
i
i
i 件物品的体积是
v
i
v_i
vi，价值是
w
i
w_i
wi。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出 最优选法的方案数。注意答案可能很大，请输出答案模
1
0
9
+
7
10^9+7
109+7 的结果。 输入格式 接下来有
N
N
N 行，每行两个整数
v
i
,
w
i
v_i,w_i
vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。 输出格式 数据范围 本题在朴素的0-1背包上，再加一个dp数组： 当
d
p
[
i
−
1
]
[
v
]
>
d
p
[
i
−
1
]
[
v
−
w
i
]
+
c
i
dp[i-1][v]>dp[i-1][v-w_i]+c_i
dp[i−1][v]>dp[i−1][v−wi]+ci：
c
n
t
[
i
]
[
j
]
=
c
n
t
[
i
−
1
]
[
j
]
cnt[i][j]=cnt[i-1][j]
cnt[i][j]=cnt[i−1][j] 有
N
N
N 件物品和一个容量是
V
V
V 的背包。每件物品只能使用一次。 第 i 件物品的体积是
v
i
v_i
vi，价值是
w
i
w_i
wi。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出 字典序最小的方案。这里的字典序是指：所选物品的编号所构成的序列。物品的编号范围是
1
…
N
1…N
1…N。 输入格式 接下来有
N
N
N 行，每行两个整数
v
i
,
w
i
v_i,w_i
vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。 输出格式 物品编号范围是
1
…
N
1…N
1…N。 数据范围 状态转移方程： 什么是多重背包？多重背包在完全背包的基础上，对每个物品加上了数量的限制，解决多重背包有两种方案，一是二进制拆分，二是单调队列优化 一个结论： 详见数据结构的单调队列专题 易错点： 一定要注意放在哪！ 有
N
N
N 个物品和一个容量是
V
V
V 的背包。 物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。 如下图所示： 每件物品的编号是
i
i
i，体积是
v
i
v_i
vi，价值是
w
i
w_i
wi，依赖的父节点编号是
p
i
p_i
pi。物品的下标范围是
1
…
N
1…N
1…N。 求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。 输出最大价值。 输入格式 接下来有
N
N
N 行数据，每行数据表示一个物品。 输出格式 数据范围 所以本题： 采用树形
d
p
dp
dp 思想，设
d
p
[
u
]
[
v
]
dp[u][v]
dp[u][v] 为以
u
u
u 为根节点，体积为
v
v
v 的最大价值，若暴力枚举子节点的话，复杂度是
O
(
2
n
)
O(2^n)
O(2n)，不可取，巧妙的做法是，把子节点
s
o
n
i
son_i
soni 看成一个一个分组，每个分组中有
v
+
1
v+1
v+1个物品，价值分别为
d
p
[
s
o
n
i
]
[
0...
v
]
dp[son_i][0...v]
dp[soni][0...v]，体积分别为
0
−
v
0-v
0−v，每个节点上跑一个分组背包即可，但最后要记得把根节点要加上！！！！！ 完整代码：
0
<
N
≤
1000
0#include
例3 [AcWing 278. 数字组合] 数字组合
第一行包含两个整数
N
N
N 和
M
M
M。
包含一个整数，表示可选方案数。
1
≤
N
≤
100
,
1le Nle100,
1≤N≤100,
1
≤
M
≤
10000
1le Mle 10000
1≤M≤10000,
1
≤
A
i
≤
1000
1le A_ile 1000
1≤Ai≤1000,
答案保证在
i
n
t
int
int 范围内
状态压缩后（同理逆序遍历）：
d
p
[
v
]
+
=
d
p
[
v
−
w
i
]
dp[v]+=dp[v-w_i]
dp[v]+=dp[v−wi]
要注意初始化：
d
p
[
0
]
=
1
dp[0]=1
dp[0]=1#include
例4 [AcWing 11. 背包问题求方案数]
第一行两个整数，
N
N
N，
V
V
V，用空格隔开，分别表示物品数量和背包容积。
输出一个整数，表示 方案数 模
1
0
9
+
7
10^9+7
109+7 的结果。
0
<
N
,
V
≤
1000
0
用
c
n
t
[
i
]
[
j
]
cnt[i][j]
cnt[i][j] 表示前
i
i
i 个物品，容量为
j
j
j 的最优方案数
主要是比较
d
p
[
i
−
1
]
[
v
]
dp[i-1][v]
dp[i−1][v] 与
d
p
[
i
−
1
]
[
v
−
w
i
]
+
c
i
dp[i-1][v-w_i]+c_i
dp[i−1][v−wi]+ci的大小：
当
d
p
[
i
−
1
]
[
v
]
<
d
p
[
i
−
1
]
[
v
−
w
i
]
+
c
i
dp[i-1][v]
c
n
t
cnt
cnt 数组同理可以状态压缩，注意初始化：
c
n
t
[
0
]
[
0...
V
]
=
1
cnt[0][0...V]=1
cnt[0][0...V]=1#include
例5 [AcWing12. 背包问题求具体方案]
第一行两个整数，
N
，
V
N，V
N，V，用空格隔开，分别表示物品数量和背包容积。
输出一行，包含若干个用空格隔开的整数，表示最优解中所选物品的编号序列，且该编号序列的字典序最小。
0
<
N
,
V
≤
1000
0
#include
二.完全背包
d
p
[
i
]
[
j
]
=
m
a
x
(
d
p
[
i
−
1
]
[
v
]
,
d
p
[
i
]
[
v
−
w
i
]
+
c
i
)
dp[i][j]=max(dp[i-1][v],dp[i][v-w_i]+c_i)
dp[i][j]=max(dp[i−1][v],dp[i][v−wi]+ci)
因此，在维度压缩时，正序遍历
相关知识与 0-1背包类似，这里不再阐述
三.多重背包
对于
n
∈
N
+
nin N^+
n∈N+，若满足
2
k
≤
n
<
2
k
+
1
(
k
≥
0
)
2^kle n<2^{k+1}(kge 0)
2k≤n<2k+1(k≥0)，那么
0
−
n
0-n
0−n 的任意数可以用一个数集
S
S
S 表示：
S
=
{
2
0
,
2
1
.
.
.
.
.
2
k
,
n
−
2
k
(
n
≠
2
k
)
}
S={ 2^0,2^1.....2^k,n-2^k(nneq 2^k )}
S={20,21.....2k,n−2k(n=2k)}
易证，略
所以可以将多重背包问题转化为0-1背包问题，时间复杂度
O
(
V
∑
i
=
1
n
l
o
g
S
i
)
O(Vsum^{n}_{i=1} logS_i)
O(V∑i=1nlogSi)#include
单调队列优化的多重背包问题
四、分组背包
例
分组背包问题与
0
−
1
0-1
0−1 背包唯一的不同的是，在于多套了一层循环，那么关键点是这层循环套在哪里呢？当压缩维度时，分组内的循环必须套在最内层，否则数据污染.#include
五、有依赖的背包问题
例1
如果选择物品
5
5
5，则必须选择物品
1
1
1 和
2
2
2。这是因为
2
2
2 是
5
5
5 的父节点，
1
1
1 是
2
2
2 的父节点。
第一行有两个整数
N
N
N，
V
V
V，用空格隔开，分别表示物品个数和背包容量。
第
i
i
i 行有三个整数
v
i
v_i
vi,
w
i
w_i
wi,
p
i
p_i
pi，用空格隔开，分别表示物品的体积、价值和依赖的物品编号。
如果
p
i
=
−
1
p_i=−1
pi=−1，表示根节点。 数据保证所有物品构成一棵树。
输出一个整数，表示最大价值。
1
≤
N
,
V
≤
100
1≤N,V≤100
1≤N,V≤100
1
≤
v
i
,
w
i
≤
100
1≤vi,wi≤100
1≤vi,wi≤100
首先为树打上
d
f
s
dfs
dfs 序标记，我们回忆一下
0
−
1
0-1
0−1 背包的状态转移方程：
d
p
[
i
]
[
j
]
=
m
a
x
(
d
p
[
i
−
1
]
[
j
]
,
d
p
[
i
−
1
]
[
j
−
v
i
]
+
w
i
)
dp[i][j]=max(dp[i-1][j],dp[i-1][j-v_i]+w_i)
dp[i][j]=max(dp[i−1][j],dp[i−1][j−vi]+wi)
即当前物品，若选或不选，都会从上一个物品的状态转移过来，即其中蕴含了上一个物品选或不选的情况
而在本题中，根据树的
d
f
s
dfs
dfs 序列，状态转移方程为（
s
i
z
[
i
]
siz[i]
siz[i] 为以
i
i
i 为
d
f
s
dfs
dfs 序编号的节点为根节点的子树大小）：
d
p
[
i
]
[
j
]
=
m
a
x
(
d
p
[
i
+
s
i
z
[
i
]
]
[
j
]
,
d
p
[
i
+
1
]
[
j
−
v
i
]
+
w
i
)
dp[i][j]=max(dp[i+siz[i]][j],dp[i+1][j-v_i]+w_i)
dp[i][j]=max(dp[i+siz[i]][j],dp[i+1][j−vi]+wi)
即：#include
方法2：分组背包
repf(j,v_,siz[u]) dp[u][j]=dp[u][j-siz[u]]+val[u];
rep(j,0,siz[u]-1) dp[u][j]=0; //防止数据污染
#include
