01背包
题目:
有 N N N 种物品和一个容量是 V V V 的背包，每种物品都只能使用一次。
第 i i i 种物品的体积是 v i v_i vi，价值是 w i w_i wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
第一行两个整数， N ， V N，V N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N N N 行，每行两个整数 v i , w i v_i,w_i vi,wi，用空格隔开，分别表示第 ii 种物品的体积和价值。
输出格式输出一个整数，表示最大价值。
数据范围
0
<
N
,
V
≤
10000
<
N
,
V
≤
1000
0 递归 + 记忆化思路: 递归枚举每一种可能 对于每一个物品 当我们背包剩余容量大于物品体积时 就有两种可能 拿或不拿 拿 当背包容量小于物品体积时 只有不拿一种可能 直接找下一个即可 核心代码 递归 + 记忆化: 动态规划: 定义
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j]为 只看前
i
i
i个物品,在背包容量为
j
j
j的情况下的最大可能 同样的 如果
j
<
v
[
i
]
j 二维: 优化: 上面的二维版本不难发现我们只使用了
d
p
[
i
]
dp[i]
dp[i]与
d
p
[
i
−
1
]
dp[i-1]
dp[i−1]的状态 定义
d
p
[
j
]
dp[j]
dp[j]为所有物品重量为
j
j
j时的最优解 并且使用
d
p
[
j
−
v
[
i
]
]
dp[j-v[i]]
dp[j−v[i]]时我们要维护
d
p
[
j
−
v
[
i
]
]
dp[j-v[i]]
dp[j−v[i]]为上一轮也就是
d
p
[
i
−
1
]
[
j
−
v
[
i
]
]
dp[i - 1][j - v[i]]
dp[i−1][j−v[i]]的值 这样
d
p
[
j
−
v
[
i
]
]
dp[j-v[i]]
dp[j−v[i]]一定是当前还没有枚举过的,也就是上一轮的值 这样的话
d
p
[
j
−
v
[
i
]
]
dp[j-v[i]]
dp[j−v[i]]一定等于之前二维的
d
p
[
i
−
1
]
[
j
−
v
[
i
]
]
dp[i - 1][j - v[i]]
dp[i−1][j−v[i]] 优化后的一维: 完全背包 题目: 有
N
N
N 种物品和一个容量是
V
V
V 的背包，每种物品都有无限件可用。 第
i
i
i 种物品的体积是
v
i
v_i
vi，价值是
w
i
w_i
wi。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 第一行两个整数，
N
，
V
N，V
N，V，用空格隔开，分别表示物品种数和背包容积。 接下来有
N
N
N 行，每行两个整数
v
i
,
w
i
v_i,w_i
vi,wi，用空格隔开，分别表示第 ii 种物品的体积和价值。 输出一个整数，表示最大价值。
0
<
N
,
V
≤
10000
<
N
,
V
≤
1000
0 思路: 这个题目与01背包非常相似,只是物品可以无限次使用 定义
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j]为前
i
i
i件物品无限使用,体积最大为
j
j
j的情况的最大值 当
j
<
v
[
i
]
j 当
j
>
=
v
[
i
]
j>=v[i]
j>=v[i]时 前面01背包使用转移为 但是这个题是可以再拿 所以
i
i
i不用减一 所以完全背包
j
>
=
v
[
i
]
j>=v[i]
j>=v[i]的转移为 代码: 优化: 前面01背包优化成一维需要维护
d
p
[
i
−
1
]
[
j
−
v
[
i
]
]
dp[i-1][j-v[i]]
dp[i−1][j−v[i]]的值,所以
j
j
j需要从大到小枚举 但是完全背包不需要维护
d
p
[
i
−
1
]
[
j
−
v
[
i
]
]
dp[i-1][j-v[i]]
dp[i−1][j−v[i]]的值 所以只需要把
j
j
j的枚举改成从小到大即可 01背包: 代码:4 5
1 2
2 4
3 4
4 5
输出样例：
8
d
p
(
n
+
1
,
s
u
m
−
v
[
n
]
)
+
v
[
n
]
dp(n+1,sum-v[n])+v[n]
dp(n+1,sum−v[n])+v[n]
不拿
d
p
(
n
+
1
,
s
u
m
)
dp(n+1,sum)
dp(n+1,sum)
两种可能取最大值即可 //背包剩余容量小于当前物品体积 直接找下一个
if (sum < v[n]) return m[n][sum][0] = dp(n + 1, sum);
//背包剩余容量大于等于当前物品体积 返回拿与不拿两种可能的最大值
m[n][sum][0] = max(dp(n + 1, sum), dp(n + 1, sum - v[n]) + w[n]);
return m[n][sum][0];
#include
当
j
>
=
v
[
i
]
j>=v[i]
j>=v[i]时 两种可能取最大值
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−v[i]]+w[i])
最后
d
p
[
N
]
[
V
]
dp[N][V]
dp[N][V]就是所有物品体积最大为
V
V
V时的最大值#include
d
p
[
i
]
[
j
]
=
m
a
x
(
d
p
[
i
]
[
j
]
,
d
p
[
i
−
1
]
[
j
−
v
[
i
]
]
+
w
[
i
]
)
;
dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
dp[i][j]=max(dp[i][j],dp[i−1][j−v[i]]+w[i]);
所有优化一维成一维数组可以直接把
[
i
]
[i]
[i]去掉
d
p
[
j
−
v
[
i
]
]
=
d
p
[
i
−
1
]
[
j
−
v
[
i
]
]
dp[j-v[i]]=dp[i - 1][j - v[i]]
dp[j−v[i]]=dp[i−1][j−v[i]]
所以我们
j
j
j得从大到小枚举#include
输出最大价值。4 5
1 2
2 4
3 4
4 5
输出样例：
10
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−v[i]]+w[i])
分拿与不拿两种情况 拿了就不能再拿了 ,所以就是
d
p
[
i
−
1
]
[
j
−
v
[
i
]
]
dp[i-1][j-v[i]]
dp[i−1][j−v[i]]
d
p
[
i
]
[
j
]
=
m
a
x
(
d
p
[
i
]
[
j
]
,
d
p
[
i
]
[
j
−
v
[
i
]
]
+
w
[
i
]
)
dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i])
dp[i][j]=max(dp[i][j],dp[i][j−v[i]]+w[i])#include
f
o
r
(
i
n
t
j
=
V
;
j
>
=
v
[
i
]
;
j
−
−
)
forquad(intquad jquad =quad V; jquad >= quad v[i];quad j--)
for(intj=V;j>=v[i];j−−)
完全背包:
f
o
r
(
i
n
t
j
=
v
[
i
]
;
j
<
=
V
[
i
]
;
j
+
+
)
forquad(intquad jquad =quad v[i]; jquad <= quad V[i];quad j++)
for(intj=v[i];j<=V[i];j++)#include
