首页 程序设计 动态规划 背包问题

# 题目大意

有 nn 件物品和一个容量是 vv 的背包，每件物品只能使用一次
第 ii 件物品的体积是 viv_i，价值是 wiw_i
问：你放进背包的最大价值是多少！

# 数据范围

  • 0<N,V≤10000 < N, V \le 1000
  • 0<vi,wi≤10000 < v_i, w_i \le 1000

# 思路

# 变量假设

dp[i][j] 表示前 ii 个物品中，已经用了 jj 的背包体积时的最大价值

# 转移方程

dp[i][j] = max(第 i 个物品放入背包的总价值，第 i 个物品不放入背包的总价值)
放入背包的前提是放得下

# 解题代码

先通过二维的来解释思路

  • 第 ii 个物品要的话，那么新价值就是 dp[i - 1][j - v[i]] + w[i]
  • 第 ii 个物品不要的话，那么新 价值就是 dp[i - 1][j]
    C++
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    void solve () {
        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 = 0; j <= m; j++) {
                dp[i][j] = dp[i - 1][j];

                if (j >= v[i])
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
            }
        }

        cout << dp[n][m] << endl;
    }

    观察有，在求 maxmax 的时候，只用到了上一层的 dp[i - 1][j - v[i]] ，所以可以优化成一维的
    C++
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    void solve () {
        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--)
                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);

        cout << dp[m] << endl;
    }