动态规划 01 背包问题详解与空间优化

背包问题概述

背包问题是一种组合优化的 NP 完全问题。给定一组物品，每种物品都有重量和价值，在限定总重量内选择物品使总价格最高。

根据物品个数分为：

• 01 背包问题：每个物品只有一个
• 完全背包问题：每个物品有无限多个
• 多重背包问题：每件物品有有限个
• 混合背包问题：包含上述三种情况
• 分组背包问题：物品分 n 组，每组最多选一个

根据是否装满分为两类：不一定装满、恰好装满。 根据限定条件个数分为：一维费用（如体积）、二维费用（如体积 + 重量）。

优化方案包括滚动数组、单调队列优化等。其中 01 背包是基础，必须掌握。

01 背包（medium）

题目描述：有一个背包，最大容量为 V。有 n 个物品，第 i 个物品体积为 vi，价值为 wi。

1. 求背包至多能装多大价值的物品？
2. 若背包恰好装满，求至多能装多大价值的物品？

输入描述：第一行两个整数 n 和 V。接下来 n 行每行两个数 vi 和 wi。 输出描述：两行答案，若无解输出 0。

第一问解题思路

状态表示

dp[i][j] 表示从前 i 个物品中选择，并且物品总体积不超过 j 时，能装入背包的最大物品价值。

状态转移方程

对于第 i 个物品，有两种选择：

1. 不选：dp[i][j] = dp[i - 1][j]
2. 选（需 j >= v[i]）：dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i])

初始化

全部初始化为 0。因为 dp[0][j] 表示无物品可放，价值为 0；dp[i][0] 表示背包空间为 0，价值为 0。

遍历顺序

从上往下，从左往右遍历。

返回值

dp[n][V]

第二问解题思路

状态表示修改

dp[i][j] 表示从前 i 个物品中选择，并且物品总体积正好等于 j 时的最大物品价值。

状态转移方程细节修改

需判断 dp[i - 1][j - v[i]] 是否能构成对应体积。设定 dp[i][j] == -1 表示无法凑成该体积，非 -1 则代表最大价值。

初始化修改

dp[0][0] = 0，其余 dp[0][i] = -1 (i > 0)。

代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = ;
 n, V, v[N], w[N];
 dp[N][N];

{
     n, V;
    cin >> n >> V;

     ( i = ; i <= n; ++i) {
        cin >> v[i] >> w[i];
    }

    
    
     ( i = ; i <= n; ++i) {
         ( j = ; j <= V; ++j) {
            dp[i][j] = dp[i - ][j];
             (j >= v[i]) {
                dp[i][j] = (dp[i][j], dp[i - ][j - v[i]] + w[i]);
            }
        }
    }
    cout << dp[n][V] << endl;

    
    (dp, , (dp));
    
     ( i = ; i <= V; ++i) {
        dp[][i] = ;
    }
     ( i = ; i <= n; ++i) {
         ( j = ; j <= V; ++j) {
            dp[i][j] = dp[i - ][j];
             (j >= v[i] && dp[i - ][j - v[i]] != ) {
                dp[i][j] = (dp[i][j], dp[i - ][j - v[i]] + w[i]);
            }
        }
    }
    cout << (dp[n][V] ==  ?  : dp[n][V]) << endl;

     ;
}