基础背包问题

Posted on | In | | Visitors:
| 文章总字数: 4.1k

前言

背包问题一直是DP的经典模型，但是像我这样的菜鸡总是学不会 （再聪明一点） 所以综合之前的做题和听课，把自己的一点感悟记录下来。（大部分与背包九讲一致）

01背包

01背包是背包模型的基础，也是我DP入门的噩梦，那就从这个问题入手吧。

题目

N件物品和一个容量为V的背包，每件物品有一个体积为c，有一个价值为v。求解背包能装入最大的价值总和。

思路

状态表示： \(f[i][j]\) 表示前i件物品放入容量为j的背包所能获得的最大价值和

状态计算：

  • 状态转移方程： \(f[i][j]=max(f[i-1][j],f[i-1][j-c[i]]+v[i])\)
  • 初始状态： \(f[i][0]=0,f[0][j]=0\)
  • 边界条件： \(j<c[i]\) 时， \(f[i][j]=f[i-1][j]\)

代码

1
2
3
4
5
6
7
8
9
10
//初始状态由于定义全局变量默认为零故不用设置
for(int i = 1; i <= N; i ++)
{
    for(int j = 0; j <= V; j++)
    {
        if(j < c[i]) f[i][j] = f[i - 1][j];//边界状态
        else f[i][j] = max(f[i - 1][j], f[i - 1][j - c[i]] + w[i]);//状态转移方程
    }
}
cout << f[N][V] << endl;

空间复杂度优化

此处的优化方法主要是观察代码与状态转移方程得出的。注意到状态转移方程中 \(f[i][j]\) 仅由 \(f[i-1][j]\) 与 \(f[i-1][j-c[i]]+w[i]\) 决定，故将第一维删去，得代码1：

1
2
3
4
5
6
7
8
9
for(int i = 1; i <= N; i ++)
{
    for(int j = 0; j <= V; j++)
    {
        if(j < c[i]) f[j] = f[j];//边界状态
        else f[j] = max(f[j], f[j - c[i]] + w[i]);//状态转移方程
    }
}
cout << f[V] << endl;

代码1存在两点问题

  • 问题1：边界状态为恒等式，删去
  • 问题2：考虑 \(i=I,j=J\) 时，此时由于内层循环是从小到大的顺序去更新，所以 \(f[J-c[I]]\) 在 \(f[J]\) 之前被 \(c[I]\) 更新了，也就是说，此时的 \(f[J-c[I]]\) 等价于二维中的 \(f[I][J-c[I]]\) 而非 \(f[I-1][J-c[I]]\) ，所以内层循环应当从大至小，又考虑边界状态，终止条件就是 \(j>=c[i]\)

更改后得一维的01背包代码：

1
2
3
4
5
6
7
8
for(int i = 1; i <= N; i ++)
{
    for(int j = V; j >= c[i]; j--)
    {
        f[j] = max(f[j], f[j - c[i]] + w[i]);//状态转移方程
    }
}
cout << f[V] << endl;

装满问题

原题设意指背包不一定装满，若要求装满，则需要将除 \(f[0]\) 外所有 \(f[j]\) 设为 \(-\infty\)

从题意角度解释，就是空间为0的背包始终视作是装满的。

也可以手算模拟，看内层循环， \(i=1\) 时，仅有 \(f[c[i]]=w[i]\) ，其余仍为负无穷。可以推断外层循环结束后，此时只要非负即可视作对于容量为 \(j\) 的背包装满。

完全背包问题

题目

一个容量为V的背包，N类物品，每类都有无限个，每个物品有一个体积为c，有一个价值为v。求解背包能装入最大的价值总和。

思路

状态表示： \(f[i][j]\) 表示前i类物品每类挑选任意个放入容量为j的背包所能获得的最大价值和

状态计算：

  • 状态转移方程： \(f[i][j]=max(f[i-1][j-k*c[i]]+k*v[i]),k\in[0,\lfloor\tfrac{V}{c[i]}\rfloor]\)
  • 初始状态： \(f[i][0]=0,f[0][j]=0\)
  • 边界条件： \(j<c[i]\) 时， \(f[i][j]=f[i-1][j]\)

代码

1
2
3
4
5
6
7
8
9
10
11
for(int i = 1; i <= N; i ++)
{
    for(int j = 0; j <= V; j ++)
    {
        for(int k = 0; k <= V / c[i]; k ++)
        {
            f[i][j]=max(f[i-1][j-k*c[i]]+k*v[i]);
        }
    }
}
cout << f[N][V] << endl;

搜索剪枝

若物品i、j满足 \(c[i]<c[j]\) 且 \(w[i]>w[j]\) ，则可以忽略物品j。该优化不能改变最坏复杂度。

降维优化

展开 \(f[i][j],f[i][j-c[i]]\) 的状态转移方程观察：

\(f[i][j]=max(f[i-1][j],f[i-1][j-c[i]]+v[i],f[i-1][j-2*c[i]]+2*v[i]...f[i-1][j-k*c[i]]+k*v[i])\)

\(f[i][j-c[i]]=max(f[i-1][j-c[i]],f[i-1][j-2*c[i]]+v[i]...f[i-1][j-k*c[i]]+(k-1)*v[i])\)

得结果 \(f[i][j]=max(f[i-1][j],f[i][j-c[i]]+v[i])\)

利用滚动数组降维，对比01背包的方程和优化知，由于此处转移方程含 \(f[i][j-c[i]]\) 所以内层循环变量j应该从小到大循环，使得 \(f[i-1][j-c[i]]\) 被更新为 \(f[i][j-c[i]]\) 进而更新 \(f[i][j]\)

二进制优化

二进制优化，在多重背包内细讲

代码

1
2
3
4
for(int i = 1; i <= N; i ++)
    for(int j = c[i]; j <= V; j ++)
        f[j]=max(f[j],f[j-c[i]]+v[i]);
cout << f[V] << endl;

对比01背包的代码，可以发现二者差别仅在内层循环，一个是从小到大，一个是从大到小，从状态和阶段的角度去解释，就是01背包当前状态是由上一阶段（ \(i-1\) ）的状态转移而来的，而完全背包的当前状态是由当前阶段已经被更新的状态（ \(i\) ）（体现出一类物品有无数个）和上一阶段（ \(i-1\) ）的状态转移而来的。

所以，因为阶段仅涉及当前和 前一个状态 所以可以使用滚动数组去优化空间

多重背包问题

题目

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

思路

状态表示： \(f[i][j]\) 表示前i类物品每类挑选不大于 \(s[i]\) 个放入容量为j的背包所能获得的最大价值和

状态计算：

  • 状态转移方程： \(f[i][j]=max(f[i-1][j-k*c[i]]+k*v[i]),k\in[0,s[i]]\)
  • 初始状态： \(f[i][0]=0,f[0][j]=0\)
  • 边界条件： \(j<c[i]\) 时， \(f[i][j]=f[i-1][j]\)

代码

1
2
3
4
5
6
7
8
9
10
11
for(int i = 1; i <= N; i ++)
{
    for(int j = 0; j <= V; j ++)
    {
        for(int k = 0; k <= V / c[i]; k ++)
        {
            f[i][j]=max(f[i-1][j-k*c[i]]+k*v[i]);
        }
    }
}
cout << f[N][V] << endl;

二进制优化

所谓的二进制优化，实质上是把多重背包转换成了01背包，转换时使用到二进制。

显然的，每一个十进制整数都可以表示成二进制形式，写成按位权和展开的形式。考虑第 \(i\) 类物品，对于 \(c[i]\) 个物品，我们将 \(c[i]\) 表示成 \(c[i]=a_0*2^0+a_1*2^1+a_2*2^2+...+a_k*2^k+C,a_i=0或1\) ，也就是说将 \(c[i]\) 件物品拆分，并按照 \(1,2,4,8,16...2^k\) 组合成新的一类物品。对于新的第 \(i\) 个物品， \(a_i=0\) 是不取，反之为取。通过这样的操作，实质上我们可以组合出取任意件第 \(i\) 类物品的情况。对于所有的物品进行此项操作后，问题转换成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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 12010, M = 2010;

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;
        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;

    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;
}

单调队列优化

由于本篇标题为背包基础，所以在这里就不深入阐述了，大概会再发一篇背包进阶来阐述这一部分以及其他类型的背包。（咕咕咕咕咕

练习题

传送门->Warma的硬币

----- 本文结束 感谢阅读 -----
0%