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