动态规划专题——背包问题

🧑‍💻 文章作者：Iareges
🔗 博客主页：https://blog.csdn.net/raelum
⚠️ 转载请注明出处

前言

本文主要介绍常见的四种背包问题，思维导图如下：

一、01背包

💡 现有件物品和一个最多能承重的背包，第件物品的重量是，价值是。在背包能承受的范围内，试问将哪些物品装入背包后可使总价值最大，求这个最大价值。

因为每件物品只有选与不选两种状态，所以该问题又称01背包问题。

设动态规划专题——背包问题的含义是：在背包承重为的前提下，从前个物品中选能够得到的最大价值。不难发现就是本题的答案。

如何计算动态规划专题——背包问题呢？我们可以将它划分为以下两部分：

选第个物品：由于第个物品一定会被选择，那么相当于从前个物品中选且总重量不超过，对应。
不选第个物品：意味着从前个物品中选且总重量不超过，对应。

结合以上两点可得递推公式：

动态规划专题——背包问题

由于下标不能是负数，所以上述递推公式要求动态规划专题——背包问题。当时，意味着第个物品无法装进背包，此时。综合以上可得出：

动态规划专题——背包问题

动态规划专题——背包问题数组应当如何初始化呢？当背包承重为时，显然装不下任何物品，所以。若一个物品也不选（即从前个物品中选），此时最大价值也是，所以。由此可知，数组应当全0初始化，即声明为全局变量。

题目链接：AcWing 2. 01背包问题

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int w[N], v[N];
int dp[N][N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];

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

    cout << dp[n][m] << "\n";

    return 0;
}

时间复杂度为动态规划专题——背包问题。