01背包

每个物品只能拿一次，求拿总容量不超过V的物品能得到的最大价值

  1. 二维状态方程：f[i][j] = max(f[i-1][j], f[i-1][j-v[i]]+w[i])，

    • f[i][j]前i个物品中容量不超过j的最大价值
    • f[i-1][j]表示不选第i个物品时，等价于求前i-1个物品容量不超过j的最大价值
    • f[i-1][j-v[i]]+w[i]，表示选第i个物品，则容量减去v[i]，价值加上w[i]

  2. 因为第i次的结果都是由第i-1次推出来的，所以可以用一维状态方程进行表示

    一维状态方程：f[j]=max(f[j], f[j-v[i]]+w[i])

  3. 如果直接按照二维的正向遍历方式遍历一维，是否等价呢？

    1
    2
    3
    4
    //以二维的方式正向遍历：
    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])
    • 假设m = 5, v[1] = 1，当外层循环到 i 的时候，内层的 j 循环1 2 3 4 5
    • 当j = 2时，判断f[2] = max(f[2], f[1] + w[i])，假设这里的f[2]更新了
    • 当j = 3时，判断f[3] = max(f[3], f[2] + w[i])，这里的f[2]用的是刚刚更新的，即f[i][2]，而并不是上一层的f[i-1][2]，因为上一层的f[i-1][2]已经被更新成当前层的f[i][2]
    • 所以，因为我们是根据上一层更新下一层，所以采用逆序遍历的方式可以避免上一层使用时已经被更新
    1
    2
    3
    4
    //以逆序的方式正向遍历：
    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])

    完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
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 = m; j >= v[i]; j--)
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    cout << f[m];
    return 0;
}

完全背包

每个物品可以使用无数次，求拿总容量不超过V的物品能得到的最大价值

  1. 与01背包不同的是，它的物品可以使用无限次

  2. 二维状态方程（后面的式子中v表示v[i]，w表示w[i]）：f[i][j] = max(f[i-1][j], f[i][j-v]+w)

    推导：

    • f[i][j] = max(f[i-1][j], f[i-1][j-v]+w,f[i-1][j-2v]+2w,……)
    • f[i][j-v] = max(f[i-1][j-v], f[i-1][j-2v]+w,f[i-1][j-3v]+2w),……
    • 由前两个式子可知：f[i][j] = max(f[i-1][j], f[i][j-v]+w)

  3. 一维状态方程：f[j] = max(f[j], f[j-v]+w)

  4. 因为我们需要的就是f[i][j-v]，所以正向遍历即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int v[N], w[N];
int f[N];
int n, m;
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++)//与01背包代码唯一不同的地方
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    cout << f[m];
    return 0;
}

多重背包

每个物品只能拿一次，每个物品最多有s件，求拿总容量不超过V的物品能得到的最大价值

  1. 如果按朴素的做法，直接每次遍历s遍即可，但是这样的时间复杂度是\(O(n^3)\)，太大
  2. 我们设想，将s件相同的物品当做独立的个体，即即使是相同的物品也视为不同的物品，那么该问题就变成了01背包问题
  3. 但是如果s的范围过大，就会导致超时，所以可以利用二进制的思想
    • 一个数s，最少需要多少个数可以将比s小的数都表示出来？
    • 答案是\(log_2s\)，以二进制的形式表示s，则每一位有取或者不取，如果s恰好是2的次方，那么可以直接用log()，但是如果不是，可以将最后一个“剩余”的数单独提出来，就可以表示完整的所有比s小的数了
  4. 将s“拆分”后，使用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
#include <bits/stdc++.h>
using namespace std;
const int N = 12010;
int v[N], w[N];
int n, m;
int f[N];
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];
    return 0;
}

分组背包

每组有若干个物品，每组只能选一个物品，求拿总容量不超过V的物品能得到的最大价值

  1. 一维状态方程：f[j] = max(f[j], f[j-v[1]]+w[1], f[j-v[2]]+w[2],……)
    • f[j]表示这一组不取
    • f[j-v[1]]表示这一组取第一个
    • 以此类推
  2. 直接三层循环遍历即可，因为是01背包的变式（只能取1个），所以j用逆序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int f[N];
int v[N][N], w[N][N], s[N];
int n, m;
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> s[i];
        for(int j = 1; 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++)
                if(v[i][k] <= j)    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
    cout << f[m];
    return 0;
}