GENIA

dp基础：背包问题

2022-12-18

dp基础：背包问题

什么是背包问题

背包问题是一种常见的动态规划问题，它涉及在限制条件下选择物品，使得选择的物品的价值最大化。

具体来说，假设你有一个有限的背包容积，并且有若干个物品，每个物品都有一个体积和一个价值。你希望选择尽可能多的物品，使得这些物品的总体积不超过背包的容积，并且总价值最大。

我们可以建立一个二维数组，其中第 $i$ 行第 $j$ 列表示将前 $i$ 个物品放进容积为 $j$ 的背包所能获得的最大价值。然后用如下的方程来求解这个问题：
$$
V_{i,j} = \max(V_{i-1,j}, V_{i-1,j-w_i}+v_i)
$$

其中，$V_{i,j}$ 表示将前 $i$ 个物品放进容积为 $j$ 的背包所能获得的最大价值，$w_i$ 和 $v_i$ 分别表示第 $i$ 个物品的体积和价值。

这个方程的意思是，对于第 $i$ 个物品，我们可以选择放或者不放，如果不放，那么最大价值就是不放的最大价值，即 $V_{i-1,j}$；如果放，那么最大价值就是放的最大价值，即 $V_{i-1,j-w_i}+v_i$。我们取这两者的较大值作为最终的结果。

用这个方程，我们就可以求出将所有物品放进容积为 $j$ 的背包中所能获得的最大价值。我们只需要枚举所有的 $j$，就可以得到最终的答案。

这种方法的时间复杂度是 $O(nV)$，其中 $n$ 是物品的数量，$V$ 是背包的容积。这个方法的空间复杂度也是 $O(nV)$，因为需要开一个 $n\times V$ 的二维数组来存储中间结果。

一个简单的例子

有这样的一组物品：

编号 1 2 3 4
体积 2 3 4 5
价值 3 4 5 6

以右下角为例，10代表背包容量为8时，放入前4个物品所能产生的最大价值。

物品编号\背包容量 0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
1 0 0 3 3 3 3 3 3 3
2 0 0 3 4 4 7 7 7 7
3 0 0 3 4 5 7 8 9 9
4 0 0 3 4 5 7 8 9 10

在填入数字10之前，我们需要考虑是否要将编号为4的物品放入背包，如果要将该物品放入，背包中就必须预留体积为5的空位，假设我们将它放入，背包的体积还剩3，问题来到了当背包容量为3时放入前3个物品所能产生的最大价值，查表得到该值为4，4+6=10。若不选择放入该物品，则最大价值依旧为9。很明显放入编号为4的物品可以得到最优解。

背包问题的分类

01背包

求解在有限的背包容量内选择物品的最优解的模型。在01背包问题中，每种物品只有一个，选或不选，也就是01的由来。上面举的例子即最简单的01背包问题。

完全背包

每种物品有无数个，可以无限次选择。

多重背包

每种物品的个数是有限且已知的。多重背包和01背包、完全背包的区别：多重背包中每个物品的个数都是给定的，可能不是一个，绝对不是无限个。

多重背包的解法是：先判断背包总容量与这个物品的容量的大小，如果背包容量小，可以完全取完，则用完全背包的思想来解决，否则将相同的物品视为不同的物品，转化为01背包问题。

代码实现

用python实现

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
# N为物品的个数，V为背包的容积
N, V = 4, 8
# v[i]和c[i]分别为第i件物品体积和价值
v = [2,3,4,5]
c = [3,4,5,6]

# 用列表生成式初始化一个全为0的数组，用于记录每种状态下的最大价值
f = [[0 for _ in range(V+1)] for _ in range(N+1)]

for i in range(1,N+1):
    for j in range(0,V+1):
        # 当物品价值大于当前背包容量，无论如何不放入
        if v[i-1] > j:
            f[i][j] = f[i-1][j]
        # 比较放入和不放入的总价值，取大的
        else:
            f[i][j] = max(f[i-1][j],(f[i-1][j-v[i-1]]+c[i-1]))

for i in range(N+1):
    print(f[i])
print(f[N][V])

'''输出：
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 3, 3, 3, 3, 3, 3, 3]
[0, 0, 3, 4, 4, 7, 7, 7, 7]
[0, 0, 3, 4, 5, 7, 8, 9, 9]
[0, 0, 3, 4, 5, 7, 8, 9, 10]
10
'''

用一维数组解决（二维数组的简化版）：

对于循环容积 j 的顺序是从 V​ 到0递减，这样可以避免在转移状态时出现被覆盖的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# n为物品的个数，V为背包的容积
n, V = 4,8
# w[i]和c[i]分别为第i件物品的重量和价值
w = [2,3,4,5]
c = [3,4,5,6]
# 初始化一个全为0的数组，用于记录每种状态下的最大价值
f = [0] * (V + 1)
# 对于每一件物品
for i in range(n):
    # 对于每一个容量
    for j in range(V, -1, -1):
        # 容量大于等于当前物品体积时，考虑当前物品是否放入背包
        if j >= w[i]:
            f[j] = max(f[j], f[j - w[i]] + c[i])
# [0, 0, 3, 4, 5, 7, 8, 9, 10]
print(f)
# 最大价值
print(f[V])
完全背包
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# n为物品的个数，V为背包的容积
n, V = 5, 9
# w[i]和c[i]分别为第i件物品的重量和价值
w = [2, 2, 6, 5, 4]
c = [6, 3, 5, 4, 6]
# 初始化一个全为0的数组，用于记录每种状态下的最大价值
f = [0] * (V + 1)
# 对于每一件物品
for i in range(n):
    # 对于每一个容量
    for j in range(c[i], V + 1):
        # 当前物品放入背包
        f[j] = max(f[j], f[j - c[i]] + w[i])
# 最大价值
print(f[V])

与 01 背包问题的实现方式基本相同，只是循环容积j的顺序从c[i]到V递增，因为每种物品有无限个，所以不需要考虑每种物品只能选择一件的限制。

多重背包

方法一：（添加k循环）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#输入两个数，分别为物品的种类数与背包容量
N,V=map(int,input().split())
#分别输入每种物品的重量、价值和件数
weight=[]
value=[]
count=[]
for i in range(N):
    w,v,c=map(int,input().split())
    weight.append(w)
    value.append(v)
    count.append(c)
#初始化dp数组
dp=[[0 for _ in range(V+1)]for _ in range(N+1)]
#动态规划
for i in range(1,N+1):
    for j in range(1,V+1):
        for k in range(0,count[i-1]+1):
            if k*weight[i-1]<=j:
                dp[i][j]=max(dp[i][j],dp[i-1][j-k*weight[i-1]]+k*value[i-1])
#输出结果
print(dp[N][V])

方法二：（暴力转化为01背包问题）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#输入两个数，分别为物品的种类数与背包容量
N,V=map(int,input().split())
#分别输入每种物品的重量、价值和件数
weight=[]
value=[]
T=0
for i in range(N):
    w,v,c=map(int,input().split())
    #硬拆成01背包
    for j in range(c):
        weight.append(w)
        value.append(v)
        T+=1
#接下来就是一个01背包了
#初始化dp数组
dp=[0 for _ in range(V+1)]
#开始动态规划
for i in range(1,T):
    for j in range(V,weight[i-1]-1,-1):
        dp[j]=max(dp[j],dp[j-weight[i-1]]+value[i-1])
print(dp[V])

当数据量过大时，暴力拆解会导致超时，因此采用二进制优化：

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
32
33
#include <iostream>
using namespace std;
#define N 12000//N*logs(注意是以2为底，s的对数)=1000*log2000≈11000，开15000保险
#define M 2010
int n,m;
int v[N],w[N];
int dp[N];//01背包优化，用一维数组
int main()
{
    int a,b,s;
    cin>>n>>m;
    int cnt=0;//存储新物品的编号
    /*多重背包二进制优化操作*/
    for(int i=1;i<=n;++i)
    {
        cin>>a>>b>>s;//第i种物品的体积，价值，数量
        int k=1;
        while(k<=s)
        {
            v[++cnt]=a*k, w[cnt]=b*k, s-=k, k*=2;
        }
        if(s>0) { v[++cnt]=a*s, w[cnt]=b*s; }
    }
    /*01背包*/
    n=cnt;//更新物品数量，此时为若干个新物品
    for(int i=1;i<=n;++i)
    {
        for(int j=m;j>=v[i];--j)
            dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
    }
    cout<<dp[m]<<endl;
    return 0;
}

用C++实现（大佬的代码）

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define MAX_N 100000
// dp[i] 表示当前背包容量为 i 时可以装的最大价值
int dp[MAX_N];
int value[10000], weight[10000], number[10000];
int bag;
// 0/1 背包
// weight 表示物品的体积，value 表示物品的价值
void ZeroOnePack(int weight, int value)
{
    // 从后往前，背包容量从大到小
    // 能装就装
    for (int i = bag; i >= weight; i--)
    {
        dp[i] = max(dp[i], dp[i - weight] + value);
    }
}
// 完全背包
// weight 表示物品的体积，value 表示物品的价值
void CompletePack(int weight, int value)
{
    // 从前往后，背包容量从小到大
    // 能装就装
    for (int i = weight; i <= bag; i++)
    {
        dp[i] = max(dp[i], dp[i - weight] + value);
    }
}
// 多重背包
// weight 表示物品的体积，value 表示物品的价值，number 表示物品的数量
void MultiplePack(int weight, int value, int number)
{
    if (bag <= number * weight)
    {
        // 如果数量比较大，转化为完全背包
        CompletePack(weight, value);
        return;
    }
    else
    {
        // 否则转化为 0/1 背包
        ZeroOnePack(weight, value);
        return;
    }
}
int main()
{
    int n;
    while (~scanf("%d%d", &bag, &n))
    {
        int i, sum = 0;
        for (i = 0; i < n; i++)
        {
            scanf("%d", &number[i]);
            scanf("%d", &value[i]);
        }
        memset(dp, 0, sizeof(dp));
        for (i = 0; i < n; i++)
        {
            MultiplePack(value[i], value[i], number[i]);
        }
        cout << dp[bag] << endl;
    }
    return 0;
}

回溯

在求解背包问题时，有时候我们需要对背包算法进行回溯，即从最优解的状态一步一步返回到初始状态，求出具体的选择方案。

回溯的过程其实很简单，我们可以从最优解的状态开始，一步一步返回到初始状态。在每一步的时候，我们都要判断当前的状态是由哪一步得到的。如果当前的状态是由放进背包的一个物品得到的，那么就将这个物品加入到选择方案中。如果当前的状态是由不放进背包的一个物品得到的，那么就跳过这个物品。最后，我们就可以得到具体的选择方案。

回溯的过程需要 O(n) 的时间复杂度，其中 n 是物品的数量。

具体实现方式如下：

1
2
3
4
5
6
7
8
# 推出被放入背包的物品
i = n
j = C
while i > 0 and j > 0:
  if dp[i][j] != dp[i - 1][j]:
    items.append(i - 1)
    j -= weights[i - 1]
  i -= 1

其中，items 是一个列表，用于存储最优解中包含的物品。

首先，设置两个变量 i 和 j 分别指向最后一个物品和背包容量。然后，在 i 和 j 均大于 0 的情况下，循环执行以下操作：

  • 如果 $dp[i][j]$ 的值不等于 $dp[i-1][j]$，则表明第 $i$ 个物品被选择了。将第 $i$ 个物品的编号加入到 items 列表中，并将 j 减去第 $i$ 个物品的体积。
  • 将 i 减 1。

循环结束后，items 列表中存储的就是最优解中包含的物品的编号。

背包问题例题练习

小明的背包1

01背包问题。

解题代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#输入物品数和背包容量
N,V=map(int,input().split())
#将物品的体积和价值分别存入列表中
weight=[]
value=[]
for i in range(N):
        w,v=map(int,input().split())
        weight.append(w)
        value.append(v)
#初始化dp数组
dp=[[0 for _ in range(V+1)] for _ in range(N+1)]
#动态规划
for i in range(1,N+1):
        for j in range(1,V+1):
		#物品本身的体积大于当前的背包容积，无论如何都不装入
		#此时该状态的最大价值与表格上位相同
                if weight[i-1]>j:
                        dp[i][j]=dp[i-1][j]
		#体积小于当前背包的体积，需要做一次比较，取最大值
                else:
                        dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i-1]]+value[i-1])
#表格右下角即为要求的最大价值
print(dp[N][V])

小明的背包2

完全背包问题。

解题代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#输入物品数和背包容量
N,V=map(int,input().split())
#将物品的体积和价值分别存入列表中
weight=[]
value=[]
for i in range(N):
        w,v=map(int,input().split())
        weight.append(w)
        value.append(v)
#初始化dp数组，这里用一维数组
dp=[0 for _ in range(V+1)]
#进行动态规划
for i in range(1,N+1):
        for j in range(weight[i-1],V+1):
                dp[j]=max(dp[j],dp[j-weight[i-1]]+value[i-1])
#最后一位即结果
print(dp[V])

小明的背包3

多重背包问题。

法一：添加k循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#输入两个数，分别为物品的种类数与背包容量
N,V=map(int,input().split())
#分别输入每种物品的重量、价值和件数
weight=[]
value=[]
count=[]
for i in range(N):
    w,v,c=map(int,input().split())
    weight.append(w)
    value.append(v)
    count.append(c)
#初始化dp数组
dp=[[0 for _ in range(V+1)]for _ in range(N+1)]
#动态规划
for i in range(1,N+1):
    for j in range(1,V+1):
        for k in range(0,count[i-1]+1):
            if k*weight[i-1]<=j:
                dp[i][j]=max(dp[i][j],dp[i-1][j-k*weight[i-1]]+k*value[i-1])
#输出结果
print(dp[N][V])

法二：拆解成01背包问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#输入两个数，分别为物品的种类数与背包容量
N,V=map(int,input().split())
#分别输入每种物品的重量、价值和件数
weight=[]
value=[]
T=0
for i in range(N):
    w,v,c=map(int,input().split())
    #硬拆成01背包
    for j in range(c):
        weight.append(w)
        value.append(v)
        T+=1
#接下来就是一个01背包了
#初始化dp数组
dp=[0 for _ in range(V+1)]
#开始动态规划
for i in range(1,T):
    for j in range(V,weight[i-1]-1,-1):
        dp[j]=max(dp[j],dp[j-weight[i-1]]+value[i-1])
print(dp[V])

关于法二的二进制优化方法：还不会（

Tags: 算法
← 贪心算法 基础数据结构 →