背包问题

2023-01-05
作者雨辰
~4.20K 字
条评论

1. 01背包
1. 1.1. 方法
2. 1.2. 空间优化
2. 完全背包
1. 2.1. 方法
2. 2.2. 空间优化
3. 多重背包

01背包

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

其中第i种物品的体积为w~i~，价值为p~i~，每种物品只有一个，

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

方法

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

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

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下的最大价值

转移方程 :

$dp[i][j] = max(dp[i-1][j] , dp[i-1][j - w_{i}] + p_{i})(j >= w_{i})$

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])

空间优化

除此之外，还可以对空间进行优化：

先来看看转移方程

$dp[i][j] = max(dp[i-1][j] , dp[i-1][j - w_{i}] + p_{i})(j >= w_{i})$

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

$dp[j] = max(dp[j] , dp[j - w_{i}] + p_{i})(j >= w_{i})$

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

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种物品的体积为w~i~，价值为p~i~，每种物品有无数个，

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

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

方法

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

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

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] = max(dp[i - 1][j],dp[i-1][j - kw_{i}]+kp_{i})(j >= kw_{i})$

来看看 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 - 3*w] + 3*p
...
dp[i - 1][j - k*w] + k*p
...
)

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

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 和上面的数据一样，将这些部分替换掉就可以得到

$dp[i][j] = max(dp[i - 1][j],dp[i][j - w] + p)$

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背包一样可以进行空间优化，还是用一个滚动数组来存储数据

看看转移方程：

$dp[i][j] = max(dp[i - 1][j],dp[i][j - w] + p)$

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

$dp[j] = max(dp[j] , dp[j - w_{i}] + p_{i})(j >= w_{i})$

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

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种物品的体积为w~i~，价值为p~i~，每种物品有s~i~个，

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

方法

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

$dp[i] = max(dp[i],dp[i-km_{i}] + kv_{i})(km_{i}<=V,k<=s_{i})$

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

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 的数量来进行拆分

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背包的思路就是完整的了

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])

单调队列优化

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

对于物品的取值：

有

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提出来，变成

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

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

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的滑动窗口（单调队列）来存储当前区间的最大值。

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是队尾一定要在队头后面

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

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

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

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

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

当有数据移除是start++

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]
现在来考虑如何出队。

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

$\frac{(k - queue[start])}{w} > s$

调整一下，就变成

$(k - queue[start]) = s * w$

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

添加元素

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

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

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

看看队列里需要存的值

$max(dp[j + kw] - kp,dp[j + (k-1)w] - (k-1)p,...,dp[j + w] - p,dp[j])$

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

如何将数据加入到队列中（存储下标，即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] - kp,dp[j + (k-1)w] - (k-1)p,...,dp[j + w] - p,dp[j]) + k_{当前}p$

那也就是

$dp[j + kw] = max(dp[j + kw] , old_dp[queue[start]] - k_{start}p + Kp)$ $k_{start} = (start - j)/w$ $k_{当前} = (K - j)/w$

d p [j + k w] = m a x (d p [j + k w], o l d_{d} p [q u e u e [s t a r t]] - (q u e u e [s t a r t] - j) / w * p + (K - j) / w * p)

$dp[j + kw] = max(dp[j + kw] , old_dp[queue[start]] - (K - queue[start])/w*p)$

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])

雨辰枫司的小栈

01背包

方法

空间优化

完全背包

方法

空间优化

多重背包

方法

二进制优化

单调队列优化