背包问题

  1. 1. 01背包
    1. 1.1. 方法
    2. 1.2. 空间优化
  2. 2. 完全背包
    1. 2.1. 方法
    2. 2.2. 空间优化
  3. 3. 多重背包
    1. 3.1. 方法
    2. 3.2. 二进制优化
    3. 3.3. 单调队列优化

01背包

有 n 种物品和一个大小为V的背包。

其中第i种物品的体积为wi,价值为pi,每种物品只有一个,

现将一些物品放入背包,在不超过背包容量的情况下,获得物品价值总和最大。

方法

定义dp[i][j] : 表示第i件物品,在j的容量下能获得的最大价值

对于每个物品,有两种选择:要么将他装进背包,要么将他舍去。那么可以划分为两种集合

1
2
3
4
5
6
7
8
9
10
11
graph TD;
1["dp[i][j] = dp[i - 1][j]"]
2["dp[i][j] = dp[i - 1][j - w] + p"]
subgraph dp
subgraph 舍弃物品i
1
end
subgraph 选择物品i
2
end
end

因为是要最大价值所以取集合的max

一轮表示第 k 件物品的选择

如果不选择物品 i,则是上一轮容量为 j 的最大价值,相当于无事发生

如果选择物品 i, 则是上一轮容量为 j - w 的最大价值加上当前物品的价值 p (因为要放下该物品需要 w 的空间, 所以需要:当前空间 - w的最大价值)

dp存储的是最大价值,所以我们需要选择两者的最大值作为当前位置的数值,即在第i个物品,在容量为j下的最大价值

转移方程 :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
n,V = map(int,input().strip().split(' '))
w = [0]
p = [0]
dp = [[0]*(V+1) for i in range(n+1)]
for i in range(n):
a,b = map(int,input().strip().split(' '))
w.append(a)
p.append(b)

for i in range(1,n + 1):
for j in range(V + 1):
dp[i][j] = dp[i - 1][j]
if j >= w[i]:
dp[i][j] = max(dp[i -1][j],dp[i - 1][j - w[i]] + p[i])

print(dp[n][V])

空间优化

除此之外,还可以对空间进行优化:

先来看看转移方程

对于更新物品 i 的值只与物品 i - 1 有关,可以用一个滚动数组进行优化。

对于容量 j 只与上一层的容量 j 和 j - w 有关,也就意味着 小容量可以影响大容量的值,即如果先更新小容量 j - w ,那么上一层容量为 j - w 的最大价值就会丢失。所以需要先更新大的值在更新小的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
n,V = map(int,input().strip().split(' '))
w = [0]
p = [0]
dp = [0] * (V+ 1)
for i in range(n):
a,b = map(int,input().strip().split(' '))
w.append(a)
p.append(b)

for i in range(1,n + 1):
for j in range(V , -1 , -1):
dp[j] = dp[j]
if j >= w[i]:
dp[j] = max(dp[j],dp[j - w[i]] + p[i])

print(dp[V])

完全背包

有 n 种物品和一个大小为V的背包。

其中第i种物品的体积为wi,价值为pi,每种物品有无数个,

现将一些物品放入背包,在不超过背包容量的情况下,获得物品价值总和最大。

与 01 背包的差别在于物品有无数个

方法

定义dp[i][j] : 表示第i件物品,在j的容量下能获得的最大价值

对于第 i 个物品我们有很多选择,要么不选,要么选 1 ,2 ,3 ,… , k , … 个,划分集合:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
graph TD;
1["dp[i][j] = dp[i - 1][j]"]
2["dp[i][j] = dp[i - 1][j - w] + p"]
3[...]
4["dp[i][j] = dp[i - 1][j - kw] + kp"]
5[...]
subgraph dp
subgraph 舍弃物品i
1
end
subgraph 选择一个物品i
2
end
subgraph ...
3
end
subgraph 选择k个物品i
4
end
subgraph ...
5
end
end

因为是要最大价值所以取集合的max

转移方程

来看看 dp[i][j]

1
2
3
4
5
6
7
8
9
max(
dp[i - 1][j]
dp[i - 1][j - 1*w] + 1*p
dp[i - 1][j - 2*w] + 2*p
dp[i - 1][j - 3*w] + 3*p
...
dp[i - 1][j - k*w] + k*p
...
)

在看看 dp[i][j - w] (其实就是吧 j 换成 j - w)

1
2
3
4
5
6
7
8
9
max(
dp[i - 1][j - 1*w]
dp[i - 1][j - 2*w] + 1*p
dp[i - 1][j - 3*w] + 2*p
dp[i - 1][j - 4*w] + 3*p
...
dp[i - 1][j - k*w] + (k - 1)*p
...
)

现在将它们放到一起看看

1
2
dp[i][j]    = max(dp[i - 1][j],dp[i - 1][j - 1*w] + 1*p,dp[i - 1][j - 2*w] + 2*p,...,dp[i - 1][j - k*w] + k*p,...)
dp[i][j -w] = max( dp[i - 1][j - 1*w] ,dp[i - 1][j - 2*w] + 1*p,...,dp[i - 1][j - k*w] + (k - 1)*p,...)

可以发现两者非常相近,dp[i][j -w] + p 和 上面的数据一样,将这些部分替换掉就可以得到

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
n,V = map(int,input().strip().split(' '))
w = [0]
p = [0]
dp = [[0]*(V+1) for i in range(n+1)]
for i in range(n):
a,b = map(int,input().strip().split(' '))
w.append(a)
p.append(b)

for i in range(1,n + 1):
for j in range(V + 1):
dp[i][j] = dp[i - 1][j]
if j >= w[i]:
dp[i][j] = max(dp[i -1][j],dp[i][j - w[i]] + p[i])

print(dp[n][V])

(哎呀,就把01背包中的dp[i - 1][j - w[i]] + p[i] 换成 dp[i][j - w[i]] + p[i])

空间优化

跟01背包一样可以进行空间优化,还是用一个滚动数组来存储数据

看看转移方程:

对于物品 i ,是 dp[i][j - w] 影响着 dp[i][j] ,即本层应该先更新 dp[i][j - w] 在更新 dp[i][j],也就是得从小到大进行更新

(其实跟01背包的完全一样,只是更新顺序不一样)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
n,V = map(int,input().strip().split(' '))
w = [0]
p = [0]
dp = [0] * (V+ 1)
for i in range(n):
a,b = map(int,input().strip().split(' '))
w.append(a)
p.append(b)

for i in range(1,n + 1):
for j in range(V + 1):
dp[j] = dp[j]
if j >= w[i]:
dp[j] = max(dp[j],dp[j - w[i]] + p[i])

print(dp[V])

(将01背包的for循环由从大到小改为从小到大,即j–改为j++)

多重背包

有 n 种物品和一个大小为V的背包。

其中第i种物品的体积为wi,价值为pi,每种物品有si个,

现将一些物品放入背包,在不超过背包容量的情况下,获得物品价值总和最大。

方法

这个问题可以转换为背包问题来解决,其中转移方程就是

dp[i]表示在当前物品之前容量为 i 的情况下能获得的最大价值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
n,V = map(int,input().strip().split(' '))
w = []
p = []
s = []
dp = [0] * (V+1)

for i in range(n):
a,b,c = map(int,input().strip().split())
w.append(a)
p.append(b)
s.append(c)

for i in range(n):
for j in range(V, -1 ,-1):
for k in range(s[i] + 1):
dp[j] = dp[j]
if j >= k * w[i]:
dp[j] = max(dp[j],dp[j - k*w[i]] + k*p[i])

print(dp[V])

二进制优化

先来看看一个数可以怎样表示,比如说13,他可以用1,2,4,6来表示(当然还可以用其他方式,比如说一个1代表1,两个1代表2,…,13个1代表13,但我们需要用尽可能少的数字来表示它)。

那是怎样拆分出1,2,4,6的呢,首先来回顾一下二进制 (15)10 = (1111)2 ,那就可以用1,2,4,8表示就可以表示0到15的数了,但(13)10 = (1101)2不能用1,4,8来表示(比如表示2)。

那怎么进行二进制拆分呢

这样我们就将13拆分成1,2,4,6。接着将物品 i 以 1,2,4,6 的数量来进行拆分

1
2
3
4
5
6
7
8
9
10
11
wAndp = []
for i in range(n):
num = 1
while s[i] > 0:
if s[i] - num >= 0:
wAndp.append([num*w[i],num*p[i]])
s[i] -= num
else:
wAndp.append([s[i]*w[i],s[i]*p[i]])
break
num *= 2

在加上01背包的思路就是完整的了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
n,V = map(int,input().strip().split(' '))
w = []
p = []
s = []
dp = [0] * (V+1)

for i in range(n):
a,b,c = map(int,input().strip().split())
w.append(a)
p.append(b)
s.append(c)

wAndp = []
for i in range(n):
num = 1
while s[i] > 0:
if s[i] - num >= 0:
wAndp.append([num*w[i],num*p[i]])
s[i] -= num
else:
wAndp.append([s[i]*w[i],s[i]*p[i]])
break
num *= 2

for i in range(len(wAndp)):
for j in range(V,-1,-1):
dp[j] = dp[j]
if j >= wAndp[i][0]:
dp[j] = max(dp[j],dp[j - wAndp[i][0]] + wAndp[i][1])

print(dp[V])

单调队列优化

我们看看如何用单调队列来优化这个代码,我们重新分析这个问题:

对于物品的取值:

1
2
3
4
5
6
dp[j]       = dp[j]
dp[j + w] = max(dp[j + w],dp[j] + p)
dp[j + 2*w] = max(dp[j + 2*w],dp[j + w] + p,dp[j] + 2*p)
dp[j + 3*w] = max(dp[j + 3*w],dp[j + 2*w] + p,dp[j + w] + 2*p,dp[j] + 3*p)
...
dp[j + k*w] = max(dp[j + k*w],dp[j + (k-1)*w] + p,...,dp[j + w] + (k - 1)*p,dp[j] + k*p)

我们可以将一些v提出来,变成

1
2
3
4
5
6
dp[j]      = dp[j]
dp[j + w] = max(dp[j + w] - p,dp[j]) + p
dp[j + 2*w] = max(dp[j + 2*w] - 2*p,dp[j + w] - p,dp[j]) + 2*p
dp[j + 3*w] = max(dp[j + 3*w] - 3*p,dp[j + 2*w] - 2*p,dp[j + w] - p,dp[j]) + 3*p
...
dp[j + k*w] = max(dp[j + k*w] - k*p,dp[j + (k-1)*w] - (k-1)*p,...,dp[j + w] - p,dp[j]) + k*p

这时我们可以发现有很多相同的量

1
2
3
4
5
dp[j]
dp[j + w] - p
dp[j + 2*w] - 2*p
...
dp[j + k*w] - k*p

我们需要找出他们的最大值

首先来看看如何找出dp[j],可以发现j,j+w,j+2w模上m后都等于j
这时可以列出下表,行是一类数据,列是同模的数据

dp[0] dp[1] dp[2] dp[w-1]
dp[0+w] dp[1+w] dp[2+w] dp[(w-1)+w]
dp[0+2w] dp[1+2w] dp[2+2w] dp[(w-1)+2w]
dp[0+3w] dp[1+3w] dp[2+3w] dp[(w-1)+3w]
dp[0+kw] dp[1+kw] dp[2+kw] dp[(w-1)+kw]

dp[j] 则是 dp[0]~dp[w-1],如果要问为什么是w-1,那就是一个数模上w必定小于w

如果找的是j ~ j+kw 的最大值那就是完全背包的问题,因为物品的数量有限,所以我们要从j ~ j + sw找最大值,从j + w ~ j + (s+1)w的最大值.所以我们需要维护一个大小为s的滑动窗口(单调队列)来存储当前区间的最大值。

1
2
3
4
5
6
7
8
9
10
for k in range(j,V + 1,w[i]):
start,end= 0,-1
if(start <= end and k - queue[start] > s[i] * w[i]):
start += 1
if start <= end:
dp[k] = max(dp[k],old_dp[queue[start]] + (k - queue[start])//w[i] * p[i])
while start <= end and old_dp[queue[end]] - (queue[end] - j)//w[i]*p[i] <= old_dp[k] - (k - j)//w[i]*p[i]:
end -= 1
end += 1
queue[end] = k

关于上面的变量解释

queue start end k w p j dp dp_old
队列 队头 队尾 当前位置 物品体积 物品价值 同余数 当前轮的数据 上一轮的数据

对于end >= start是队尾一定要在队头后面

1
2
3
4
5
6
7
8
graph LR;
subgraph queue
1[null] --> 2[null] --> 3[null] --> 4[null]
end
subgraph N
start -.-> 1
e[end] -.-> -1
end

开始的时候end指向的是一个空位置,当有数据加入时end++ 在将数据填入queue
,即:

1
2
3
4
5
6
7
8
graph LR;
subgraph queue
1[1] --> 2[null] --> 3[null] --> 4[null]
end
subgraph N
start -.-> 1
e[end] -.-> 1
end

1
2
3
4
5
6
7
8
graph LR;
subgraph queue
1[1] --> 2[2] --> 3[null] --> 4[null]
end
subgraph N
start -.-> 1
e[end] -.-> 2
end

1
2
3
4
5
6
7
8
graph LR;
subgraph queue
1[1] --> 2[2] --> 3[3] --> 4[null]
end
subgraph N
start -.-> 1
e[end] -.-> 3
end

当有数据移除是start++

1
2
3
4
5
6
7
8
graph LR;
subgraph queue
1[1] --> 2[2] --> 3[3] --> 4[null]
end
subgraph N
start -.-> 2
e[end] -.-> 3
end

这样就实现了一个双端队列

接着我们需要把数据存入这样一个队列,原则是这个队列必须是单调的,即 queue[i] > queue[i-1]queue[i] > queue[i-1]
现在来考虑如何出队。

我们需要维护一个大小固定的队列,即当前队头的位置不在维护的窗口时,我们就将队头的元素出队,即:

调整一下,就变成

当满足这个式子时start++,即从队头出队。

添加元素

我们需要维护这个队列的单调性,这入队时需要考虑队尾元素是否与我们入队的元素大小关系

如果是单调递增则(队尾 >= 入队),则弹出队尾元素,直到不满足为止

如果是单调递减则(队尾 <= 入队),则弹出队尾元素,直到不满足为止

看看队列里需要存的值

需要存的是下标最大值,则需要用到单调递减的单调队列

如何将数据加入到队列中(存储下标,即j+kw)也就是将 dp[j+kw] - kp 加入,当队尾 dp[queue[end]] - (queue[end] - j) / w * p <= dp[k] - (k - j) / w * p 时(这里的dp是上一轮的数据),弹出元素,直到满足为止,在把元素加入队列中

接着考虑如何更新,在来看看dp是如何更新的:

那也就是



dp[j+kw]=max(dp[j+kw],olddp[queue[start]](queue[start]j)/wp+(Kj)/wp)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
n , V = map(int,input().strip().split())
w = []
p = []
s = []
dp = [0]*(V + 1)
queue = [0]*(V + 1)

for i in range(n):
a,b,c = map(int, input().strip().split())
w.append(a)
p.append(b)
s.append(c)

for i in range(n):
for j in range(w[i]):
old_dp = dp.copy()
for k in range(j,V + 1,w[i]):
start,end= 0,-1
if(start <= end and k - queue[start] > s[i] * w[i]):
start += 1
if start <= end:
dp[k] = max(dp[k],old_dp[queue[start]] + (k - queue[start])//w[i] * p[i])
while start <= end and old_dp[queue[end]] - (queue[end] - j)//w[i]*p[i] <= old_dp[k] - (k - j)//w[i]*p[i]:
end -= 1
end += 1
queue[end] = k

print(dp[V])