背包问题 | 山暮云秋

01 背包-采药

采药

1、采药：输入 $T$ 和 $M$ 分别表示拥有的总时间和药材种类($T \leq 1000, M \leq 100$)，对于每种药材，输入 $t_i$ 和 $v_i$ ($t_i,v_i \leq 100$)，表示采摘该药材需要的时间和药材的价值，每种药材只可采摘一次。可能输入多组数据，直到 $T$ 和 $M$ 都为 $0$ 结束。对于每组数据，输出其规定时间内能采摘的药材价值之和的最大值
2、对于每种药材都可以用 $0$ 或 $1$ 标记状态(是否被选择)，是一个01 背包问题。运用动态规划的思想，先确定状态：令 $dp[i][j]$ 表示到第 $i$ 个物品为止，用了 $j$ 的时间，所获得的最大价值
3、再确定转移，对于当前的 $dp[i][j]$ ，有两种情况：如果没选择当前第 $i$ 个物品，则 $dp[i][j] = dp[i-1][j]$ (没有花费时间，没有增加价值，和上一个——到第 $i-1$ 个物品的状态相同)；如果选择了当前第 $i$ 个物品，则 $dp[i][j] = dp[i-1][j-t[i]] + v[i]$(当前状态等同于 $dp[i-1][j-t[i]]$ 上一个物品的价值 + 当前物品价值，其中因为当前 $dp[i][j]$ 花费的总时间为 $j$，所以上一个物品的时间应为 $j-t[i]$)。总结状态转移方程为：
$$dp[i][j] = \left\{ \begin{array}{l} dp[i-1][j]&,没选择当前物品 \\ \\ dp[i-1][j-t[i]] + v[i]&,选择了当前物品 \\ \end{array} \right. $$
4、最后确定初始化和边界：初始化 $dp[0][i] = 0$(到第 $0$ 个物品无论花费多少时间，价值为 $0$)；边界为 $i \leq M, j \leq T$

代码实现

#include <bits/stdc++.h>
using namespace std;

int T, M;
int dp[110][1010]; // dp[i][j] 表示到第 i 个物品花费 j 的时间的最大价值
int t[110], v[110];

void solve()
{
    // 初始化
    for (int i = 0; i <= T; i++)
        dp[0][i] = 0;

    // 输入
    for (int i = 1; i <= M; i++)
        cin >> t[i] >> v[i];

    // 注意转移方程中，其中一种为 dp[i][j] = dp[i-1][j-t[i]] + v[i]，令 i_ = i-1，j_ = j-t[i]
    // 则隐含 i_ < i, j_ < j，所以遍历方向一定要从小到大
    // 状态转移，dp[i][j] = dp[i-1][j] 或 dp[i-1][j-t[i]] + v[i]，取大值
    for (int i = 1; i <= M; i++)
    {
        for (int j = 0; j <= T; j++)
        {
            // 注意判断时间的合法性，不要越界
            if (j - t[i] >= 0)
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - t[i]] + v[i]);
            else
                dp[i][j] = dp[i - 1][j];
        }
    }

    // 输出，到第 M 个物品花费 T 时间的最大价值
    cout << dp[M][T] << '\n';
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    while (cin >> T >> M)
    {
        if (T == 0 && M == 0)
            break;
        solve();
    }
    return 0;
}

滚动数组优化

1、回顾之前的思路中，$dp[i][j]$ 所需的值只有 $dp[i-1][j]$ 与 $dp[i-1][j-t[i]]$ ，而当更新完当前 $dp[i][j]$ 后，前一行即 $dp[i-1]$ 行就不需要了。因此，实际需要的行数只需要两行，一行表示当前行，一行表示前一行
2、由于数组的拷贝又需要开销，所以可以换一种方法实现。只开两行的数组 $dp[0][]$ 与 $dp[1][]$，当前更新第 $0$ 行时就由第 $1$ 行的状态转移过来，反之亦然。这样交替更新，就实现了滚动数组，节省空间
3、具体地，可以通过奇偶性或位运算实现。用 $cur = i \land 1$ 标记哪一行表示当前行，则 $cur \oplus 1$ 即为另一行(上一行)。最后输出时即输出最后一行 $cur$ 的那一行，即 $dp[M \land 1][T]$

#include <bits/stdc++.h>
using namespace std;

int T, M;
int dp[2][1010]; // dp[i][j] 表示到第 i 个物品花费 j 的时间的最大价值
int t[110], v[110];

void solve()
{
    // 初始化
    for (int i = 0; i <= T; i++)
        dp[0][i] = 0;

    // 输入
    for (int i = 1; i <= M; i++)
        cin >> t[i] >> v[i];

    // 注意转移方程中，其中一种为 dp[i][j] = dp[i-1][j-t[i]] + v[i]，令 i_ = i-1，j_ = j-t[i]
    // 则隐含 i_ < i, j_ < j，所以遍历方向一定要从小到大
    // 状态转移，dp[i][j] = dp[i-1][j] 或 dp[i-1][j-t[i]] + v[i]，取大值
    for (int i = 1; i <= M; i++)
    {
        // 滚动数组优化，cur 表示当前行，cur ^ 1 表示上一行(另一行)
        int cur = i & 1;

        for (int j = 0; j <= T; j++)
        {
            // 注意判断时间的合法性，不要越界
            if (j - t[i] >= 0)
                dp[cur][j] = max(dp[cur ^ 1][j], dp[cur ^ 1][j - t[i]] + v[i]);
            else
                dp[cur][j] = dp[cur ^ 1][j];
        }
    }

    // 输出，到第 M 个物品(最后一行的 cur = M & 1)花费 T 时间的最大价值
    cout << dp[M & 1][T] << '\n';
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    while (cin >> T >> M)
    {
        if (T == 0 && M == 0)
            break;
        solve();
    }
    return 0;
}

一维优化

1、在滚动数组中 $dp[cur][j] = max(dp[cur \oplus 1][j], dp[cur \oplus 1][j - t[i]] + v[i])$ ，其本质可看作先将上一行复制到当前行，再进行转移比较，因此可以再将其压缩为一维(省去了复制的步骤)，$dp[j]$ 表示到目前为止，花费了 $j$ 时间的最大价值
2、此时转移方程变为 $dp[j] = max(dp[j], dp[j - t[i]] + v[i])$ ，但转移时应使用上一行时的数据，如果自左向右遍历，左侧的数据已被更新(即 $dp[j - t[i]]$ 已经变为当前行数据)。因此要自右向左遍历，范围从最大时间开始，始终满足 $j - t[i] \geq 0$

#include <bits/stdc++.h>
using namespace std;

int T, M;
int dp[1010]; // dp[j] 表示到当前为止花费 j 的时间的最大价值
int t[110], v[110];

void solve()
{
    // 初始化
    for (int i = 0; i <= T; i++)
        dp[i] = 0;

    // 输入
    for (int i = 1; i <= M; i++)
        cin >> t[i] >> v[i];

    // 状态转移，dp[j] = max(dp[j], dp[j - t[i]] + v[i])
    for (int i = 1; i <= M; i++)
        // j 自右向左遍历，注意转移范围要保证 j - t[i] >= 0
        for (int j = T; j - t[i] >= 0; j--)
            dp[j] = max(dp[j], dp[j - t[i]] + v[i]);

    // 输出，到最后花费 T 时间的最大价值
    cout << dp[T] << '\n';
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    while (cin >> T >> M)
    {
        if (T == 0 && M == 0)
            break;
        solve();
    }
    return 0;
}

完全背包-无穷背包

无穷背包

1、无穷背包：给定容积为 $m$ 的背包($m \leq 10^5$)，有 $n$ 种商品($n \leq 500$)，每种商品价值为 $w_i$ ($w_i \leq 10^9$)，体积为 $v_i$ ($v_i \leq m$)。若商品数量无限且可以重复放入同一商品，输出最多可以带走多少价值的物品
2、与上一题不同，每件物品可以重复选择，是完全背包问题。运用动态规划的思想，先确定状态：令 $dp[i][j]$ 表示到第 $i$ 个物品为止，用了 $j$ 的容积，所获得的最大价值
3、再确定转移，对于当前的 $dp[i][j]$ ，有两种情况：如果没选择当前第 $i$ 个物品，则 $dp[i][j] = dp[i-1][j]$ (没有花费容积，没有增加价值，和上一个——到第 $i-1$ 个物品的状态相同)，其相当于选择了 $0$ 个第 $i$ 个物品；如果选择了当前第 $i$ 个物品，则 $dp[i][j] = dp[i][j-v[i]] + w[i]$ (当前状态等同于 $dp[i][j-v[i]]$ 当前行当前个数$-1$ 个物品的价值 + 当前物品价值，其中因为当前 $dp[i][j]$ 花费的总容积为 $j$，所以当前数量$-1$ 个物品的容积应为 $j-v[i]$)。总结状态转移方程为：
$$dp[i][j] = \left\{ \begin{array}{l} dp[i-1][j]&,没选择当前物品 \\ \\ dp[i][j-v[i]] + w[i]&,选择了当前物品 \\ \end{array} \right. $$
4、最后确定初始化和边界：初始化 $dp[0][i] = 0$ (到第 $0$ 个物品无论花费多少容积，价值为 $0$)；边界为 $i \leq n, j \leq m$
5、由于朴素算法的数组大小过大，所以栈空间不足，需要用滚动数组优化为 $2$ 行的数组

代码实现

#include <bits/stdc++.h>
using namespace std;

const int N = 510;
const int A = 1e5 + 10;

int m, n;       // 容积和商品种类
int dp[N][A];   // 到第 i 个物品花费 j 容积的最大价值
int w[N], v[N]; // 商品价值和体积

void solve()
{
    cin >> m >> n;

    // 初始化
    for (int i = 0; i <= m; i++)
        dp[0][i] = 0;

    // 输入
    for (int i = 1; i <= n; i++)
        cin >> w[i] >> v[i];

    // 状态转移
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= m; j++)
        {
            if (j - v[i] >= 0)
                dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i]);
            else
                dp[i][j] = dp[i - 1][j];
        }
    }

    // 输出
    cout << dp[n][m] << '\n';
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--)
        solve();
    return 0;
}

滚动数组优化

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 510;
const int A = 1e5 + 10;

int m, n;       // 容积和商品种类
int dp[2][A];   // 到第 i 个物品花费 j 容积的最大价值
int w[N], v[N]; // 商品价值和体积

void solve()
{
    cin >> m >> n;

    // 初始化
    for (int i = 0; i <= m; i++)
        dp[0][i] = 0;

    // 输入
    for (int i = 1; i <= n; i++)
        cin >> w[i] >> v[i];

    // 状态转移
    for (int i = 1; i <= n; i++)
    {
        // 滚动数组优化：当前行为 cur，上一行为 cur ^ 1
        int cur = i & 1;

        for (int j = 0; j <= m; j++)
        {
            if (j - v[i] >= 0)
                dp[cur][j] = max(dp[cur ^ 1][j], dp[cur][j - v[i]] + w[i]);
            else
                dp[cur][j] = dp[cur ^ 1][j];
        }
    }

    // 输出，最后一行的 cur = n & 1
    cout << dp[n & 1][m] << '\n';
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--)
        solve();
    return 0;
}

多重背包-多重背包

多重背包

1、多重背包：给定容积为 $m$ 的背包，有 $n$ 种商品($m,n \leq 100$)，其中每种商品只有 $s_i$ 件，价值为 $w_i$，体积为 $v_i$($s_i,w_i,v_i \leq 100$)。若可以重复放入同一商品，输出最多可以带走多少价值的物品
2、多重背包可以看作商品限量的完全背包。对于每种商品有 $s_i$ 件，可以将其展开为 $s_i$ 件单独的只能选 $1$ 次的商品，即如有 $3$ 件商品 $A$，可看作有 $3$ 个只能选 $1$ 次的商品 $A$，此时即将其转化为01 背包解决
3、实际实现中，并不会将展开的商品存储下来，而是读到一件商品，跑 $s[i]$ 遍一维 01 背包。但注意，只适合数据量较小的情况

代码实现

#include <bits/stdc++.h>
using namespace std;

const int N = 110;
int dp[N]; // 一维 01 背包，到当前为止花费 j 容量的最大价值

void solve()
{
    int m, n;
    cin >> m >> n;

    for (int i = 1; i <= n; i++)
    {
        int s, w, v;
        cin >> s >> w >> v;

        // 执行 s 次 01 背包
        while (s--)
            // 一维 01 背包
            for (int j = m; j - v >= 0; j--)
                dp[j] = max(dp[j], dp[j - v] + w);
    }

    // 输出到最后花费 m 容积的最大价值
    cout << dp[m];
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--)
        solve();
    return 0;
}

二进制优化

1、多重背包二周目：在上题基础上，改为了 $n_i,m_i,s_i \leq 2000$
2、由于原思路时间复杂度 $O(n*m*s_i)$，一定超时。原先的拆分思路为将 $s_i$ 拆分为 $s_i$ 个 $1$ 相加，再来表示选择 $[0, s_i]$ 个物品的情况(如 $84$ 个商品相当于从中选 $84$ 个 $1$ 个商品相加表示)
3、那么便可以用二进制拆分的方式优化，从二进制低位向高位拆分，剩余不够拆的放在最后，例如 $s_i = 116$ 时可拆分为 $s_i = 1 + 2 + 4 + 8 + 16 + 32 + 53$ ，这样选择 $[0, s_i]$ 个物品一定能够被这些数组合得到(如 $84 = 1 + 2 + 4 + 8 + 16 + 53$ )，也可以达到原思路相同的效果
4、此时执行01 背包时，可看作拆分出的商品被打包在一起，如上 $s_i = 116$ 时即对 $1, 2, 4, 8, \ldots, 53$ 个商品进行选择(其 $w_i,v_i$ 也对应地 $\times 1, \times 2, \times 4, \times 8, \ldots, \times 53$)

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 2010;
int dp[N]; // 一维 01 背包，到当前为止花费 j 容量的最大价值

void solve()
{
    int m, n;
    cin >> m >> n;

    for (int i = 1; i <= n; i++)
    {
        int s, w, v;
        cin >> s >> w >> v;

        vector<int> vec; // 记录 s 的拆分
        // 从二进制低位向高位拆分 s
        int x = 1;
        while (s >= x)
        {
            vec.push_back(x);
            s -= x;
            x <<= 1;
        }
        // 如果还有剩余，也加入 vec
        if (s)
            vec.push_back(s);

        // 从 vec 中取 k 作为系数，用于表示 [0, s] 之间的所有可能
        for (int &k : vec)
            // 一维 01 背包(注意范围，v 也要乘系数)
            for (int j = m; j - k * v >= 0; j--)
                dp[j] = max(dp[j], dp[j - k * v] + k * w);
    }

    // 输出到最后花费 m 容积的最大价值
    cout << dp[m];
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--)
        solve();
    return 0;
}

01 背包-采药

完全背包-无穷背包

多重背包-多重背包

页底评论