0%

算法基础（14）

发表于 分类于 本文字数： 7k
第五章 动态规划的内容：背包问题

背包问题

动态规划（Dynamic Programming，DP）的常见模型：背包问题，其核心在于状态的表示和状态的转移。

背包问题：有$N$个物品和一个容量为$V$的背包，每个物品有重量$v_i$和价值$w_i$两种属性，要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。

可参考：OI Wiki-背包DP

1. 01背包

01背包问题的特点是每件物品最多只能用一次

例题：01背包问题（Acwing 2）

有$N $件物品和一个容量是$V$的背包。每件物品只能使用一次。第$i$件物品的体积是$v_i$，价值是$w_i$。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。

数据范围：$0<N,V≤1000,0<v_i,w_i≤1000$。

DP问题一般从两个角度来考虑：

  • 状态表示：背包问题有两维，$f(i, j)$，再进一步：

    • $f(i,j)$表示的集合是什么，表示所有选法，需满足两个条件：（1）只从前$i$个物品中选，（2）选出的物品的总体积$\le j$
    • 集合的属性是什么，（最大值，最小值，元素的数量），对于背包问题显然是：所有选法的价值的最大值

  • 状态计算：对应集合的划分，考虑$f(i,j)$可以怎样计算出来，把当前的集合能划分成若干个更小的子集，每个子集都可以用前面更小的子集表示出来。对于背包问题，我们把$f(i,j)$分为两个子集：

    • 不含$i$；只从前$i-1$个物品中选，且总体积$\le j$，即$f(i-1,j)$；
    • 含$i$：从前$i$个物品中选，且总体积$\le j$，且要包含物品$i$；这里需要绕个弯，每种选法中都有物品$i$，那我们可以从每种选法中减去$i$，即总体积$\le j - v_i$，且这样不会影响不同选法中的最大值是哪个，即问题转化成立从前$i-1$个物品中选，且总体积$j - v_i$，最后再加上物品$i$的价值，即$f(i-1, j -v_i)+w_i$。

    集合的划分一般遵循两个原则：（1）不重；（2）不漏

DP的优化一般是对DP问题的代 码或计算方程作等价变形，所以做DP问题时一定要把基本的方程形式写出来，再做优化。

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
#include<iostream>
using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][N];

int main()
{
    cin >> n >> m;   //n表示物品数量，m表示背包容积
    
    for(int i = 1; i <= n; i ++)
        cin >> v[i] >> w[i];
    
    //从f[0][0]到f[0][m]都是0，因为没选任何物品；全局变量已经是0了，所以下面从1开始
    for(int i = 1; i <= n; i ++)
        for(int j = 0; j <= m; j ++)
        {
            f[i][j] = f[i - 1][j];    //不含i的子集一定存在
            if(j >= v[i])             //当j大于v[i]时，含i的子集才存在  
                f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }
    
    cout << f[n][m] << endl;
    
    return 0;
}

上面的代码是用二维的f[i][j]来表示状态的，其实那可以进一步优化，用一维数组来做。$f(i,j)$这一层的计算只用到了$f(i-1,)$，$f(,j)$只用到了$f(,j)$和$f(,j-v_i)$，都是$\le j$的。下面对代码进行等价变形即可：

  1. 将二维的f[N][N]变为一维的f[N]；

  2. f[i][j] = f[i - 1][j]; 等价为f[j] = f[j]; 可以直接删掉；

  3. if(j >= v[i]) 等价于让j直接从j = v[i] 开始循环；

  4. 如果直接把f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);改成f[j] = max([j], f[j - v[i]] + w[i]);，是不对的；因为j-v[i]是小于j的，在第i层中，计算到这里时它已经在层内被更新过了，f[j-v[i]]存的其实是第i层的f[j-v[i]]。而我们实际需要的是第i-1层的f[j-v[i]]，因此要在第i层计算到它时在层内还没有被更新过。为此我们只需要把j从大到小遍历，即for(int j = m; j >= v[i]; j --)。（太妙了）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N];

int main()
{
    cin >> n >> m;   //n表示物品数量，m表示背包容积
    
    for(int i = 1; i <= n; i ++)
        cin >> v[i] >> w[i];
    
    for(int i = 1; i <= n; i ++)
        for(int j = m; j >= v[i]; j --)
			f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[m] << endl;
    
    return 0;
}

2. 完全背包

完全背包问题的特点是每件物品有无限个，即可以在背包中放多个相同物品。

例题：完全背包问题（ACwing 3）

有$ N $种物品和一个容量是$ V $的背包，每种物品都有无限件可用。第$ i $种物品的体积是$ v_i$，价值是$ w_i$。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。

数据范围：$0<N,V≤1000,0<v_i,w_i≤1000$

朴素做法的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
using namespace std;

const int  N = 1010;
int n,m;
int v[N], w[N];
int f[N][N];

int main()
{
    cin >> n >> m;
    
    for(int i = 1; i <= n; i ++)
        cin >> v[i] >> w[i];
    
    for(int i = 1; i <= n; i ++)
        for(int j = 0; j <= m; j ++)
            for(int k = 0; k * v[i] <= j; k ++)
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);

    cout << f[n][m] << endl;
    
    return 0;
}

优化：比较计算f[i,j]和f[i,j-v]的状态方程，f[i,j-v]的每一项与f[i,j]的对应项很相似，只是少了一个w，则橙色框中的最大值就等于f[i,j-v]+w，因此有f[i,j]=max(f[i-1,j], f[i,j-v]+w)，这样在计算f[i,j]时就只需枚举两个状态，而不是k个状态

比较01背包问题的方程：f[i,j]=max(f[i-1][j], f[i-1, j-v]+w[i])，只有一点不同。

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
#include<iostream>
using namespace std;

const int  N = 1010;
int n,m;
int v[N], w[N];
int f[N][N];

int main()
{
    cin >> n >> m;
    
    for(int i = 1; i <= n; i ++)
        cin >> v[i] >> w[i];
    
    for(int i = 1; i <= n; i ++)
        for(int j = 0; j <= m; j ++)
        {
            f[i][j] = f[i - 1][j];
            if(j >= v[i])  f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
        }

    cout << f[n][m] << endl;
    
    return 0;
}

再优化：同样地，完全背包问题也可以优化到用一维数组做，用01背包问题相同的思路即可，而且完全背包的方程：f[i,j]=max(f[i-1,j], f[i,j-v]+w)，是用第i层的数据更新，因此遍历j时从小到大遍历即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
using namespace std;

const int  N = 1010;
int n,m;
int v[N], w[N];
int f[N];

int main()
{
    cin >> n >> m;
    
    for(int i = 1; i <= n; i ++)
        cin >> v[i] >> w[i];
    
    for(int i = 1; i <= n; i ++)
        for(int j = v[i]; j <= m; j ++)
            f[j] = max(f[j], f[j - v[i]] + w[i]);
  

    cout << f[m] << endl;
    
    return 0;
}

3.多重背包

多重背包问题的特点是每件物品有有限个数，既不是1件也不是无限件，它有个确定的数值。

状态转移方程：f[i][j]=max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k); k = 0,1,2,...,s[i]

例题：多重背包问题I（Acwing 4）

有$N$种物品和一个容量是$V$的背包。第$i$种物品最多有$s_i$件，每件体积是$ v_i$，价值是$ w_i$。求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输出最大价值。

数据范围：$0<N,V≤100,0<v_i,w_i,s_i≤100$

朴素做法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
using namespace std;

const int N = 110;

int n, m;
int v[N], w[N], s[N];
int f[N][N];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
        cin >> v[i] >> w[i] >> s[i];
    
    for(int i = 1; i <= n; i ++)
        for(int j = 0; j <= m; j ++)
            for(int k = 0; k <= s[i] && k * v[i] <= j; k ++)
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
    
    cout << f[n][m] << endl;
    
    return 0;
}

这道题的数据范围比较小，所以暴力做法也不会超时。若是将数据范围改为：

$0<N≤1000,0<V≤2000,0<v_i,w_i,s_i≤2000$，（Awcing 5 多重背包问题2）

大约要算$100020002000=40$亿次，暴力做法一定会超时（c++一秒大约能算一亿次，即$10^9$次）

优化：同样从f[i,j]和f[i,j-v]的状态转移方程入手

发现两式的中间一部分是相似的，但f[i,j-v]中最后有一项f[i-1, (s+1)v]+sw，因此无法直接使用完全背包的优化思路来解决。比如我们已知了1到n个数的最大值和第n个数的值，要求前1到n-1个数的最大值，是无法求出来的，即max()函数无法做“减法”，所以我们不能直接用完全背包的优化问题来优化这个多重背包的问题（？不太懂）。

那要如何优化呢，这里用到了一种“二进制”的方法。假设第i个物品有$s=1023$个，我们想去求它放入背包后的最大值，那真的需要去从0枚举到1023嘛，其实是没必要的。我们可以把这个物品“打包”成若干组，每组分别有$1,2,4,8,\dots,512$，每一组最多只能选一次，我们可以用这10组来拼凑出$1 \sim 1023$中的任何一个数；这样每组背包有选或不选两种状态，就可以转化为01背包问题中的一个物品（只能选一次），我们枚举新的物品选或不选，就可以拼凑出第i个物品的所有方案了。原来需要枚举1024次，现在只需枚举10次，这样就把朴素代码中第18行中，$O(n)$的复杂度优化为了$O(\log n)$。

对于一个一般的$s$，可以这样分组：$1, 2, 4, 8, \dots, 2^k, c$，其中$2^k \le s, c < 2^{k+1}$，从$1$到$2^k$可以凑出$0 \sim 2^{k+1} -1$中任意的数，加上$c$后可以凑出$c \sim 2^{k+1}-1+c$中任意的数，则$2^{k+1}-1+c=s$。而区间$[0,2^{k+1}-1]$和$[c,s]$一定有交集，即合并起来没有“空隙”，因为$c$是严格小于$2^{k+1}$的。

理一下思路：对于第$i$个物品有$s_i$个，我们把它分为$\log s_i$组（上取整），转化为01背包问题，这样就把朴素做法的时间复杂度从$O(n\cdot v \cdot s)$优化到了$O(n \cdot v \cdot \log s_i)$。对于本题的数据范围：$1000 2000 \log 2000=2*10^7$，是满足要求的。

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
#include<iostream>
using namespace std;

const int N = 12010, M = 2010;   // 1000 * log 2000 = 12000

int n, m;
int v[N], w[N];
int f[M];

int main()
{
    cin >> n >> m;
    
    int cnt = 0;   //记录分组后的新的“物品”的序号
    for(int i = 1; i <= n; i ++)
    {
        int a, b, s;    //物品i的体积，价值，个数
        cin >> a >> b >> s;
        int k = 1;
        while(k <= s)
        {
            cnt ++;
            v[cnt] = a * k;
            w[cnt] = b * k;
            s -= k;
            k *= 2;
        }
        if(s > 0)
        {
            cnt ++;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }
    
    n = cnt;
    
    //套用01背包问题代码即可
    for(int i = 1; i <= n; i ++)
        for(int j = m; j >= v[i]; j --)
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    
    cout << f[m] << endl;
            
    return 0;
}

4.分组背包

分组背包问题的特点是由若干组物品，每一组中最多只能选一个物品。

例题：分组背包问题（Acwing 9）

有 $N $组物品和一个容量是 $V$ 的背包。每组物品有若干个，同一组内的物品最多只能选一个。每件物品的体积是$ v_{ij}$，价值是$ w_{ij}$，其中$ i $是组号，$j$ 是组内编号。求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。输出最大价值。

数据范围：数据范围：$0<N,V≤100,0<S_i≤100,0<v_{ij},w_{ij}≤100$

分析的思路和前面的类似，也是从状态表示和状态计算两个角度来分析。完全背包问题枚举的是第$i$个物品选几个，分组背包问题是枚举第$i$组物品选哪个。

背包问题的小Tip：若在状态转移时，用的上一层的状态就从大到小枚举体积；若是用的本层的状态就从小到大枚举体积。

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
#include<iostream>
using namespace std;

const int N = 110;

int n, m;
int v[N][N], w[N][N], s[N];   //s[]存每一组的个数
int f[N];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        cin >> s[i];
        for(int j = 0; j < s[i]; j ++)
            cin >> v[i][j] >> w[i][j];
    }
    
    for(int i = 1; i <= n; i ++)
        for(int j = m; j >= 0; j --)
            for(int k = 0; k < s[i]; k ++)   //枚举第i组物品中所有的选择
                if(v[i][k] <= j)
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
    
    cout << f[m] << endl;
    
    return 0;
}