题解 | #01背包问题入门详细注释#

#include <iostream>
#include <string.h>

using namespace std;

const int N = 1010;
// 定义物品个数和背包体积，以及每个物品的对应的体积和价值，定义成全局可以直接初始化为0
int n, V, v[N], w[N];
// 1. dp[i][j]表示从1~i个物品中选取，背包容量为j的所有选择中，背包所能装的最大价值
// 2. dp[i][j]表示从1~i个物品中选取，背包容量恰好等于j的所有选择中，背包所能装的最大价值
int dp[N][N];

int main()
{
    // 读入数据
    cin >> n >> V;
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];
    // 1. 解决第一问，背包不需要装满的最大价值
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= V; j++)
        {
            // dp[i][j]可由两种状态推导而来，选取i物品和不选取i物品
            // 1. 背包一定存在不选取i物品的情况，所以可直接把最大价值暂时赋值为dp[i-1][j](从0~(i-1)个物品中选取，背包容量为j的最大价值)
            dp[i][j] = dp[i - 1][j];
            // 2. j-v[i]>=0则表示容量为j可以装下i物品，即存在选取i物品的状态，加上i物品的价值
            // 选取i物品后，背包容量j减去i物品体积，再到1~(i-1)的物品中，容量为j-v[i]的情况下找最大
            if (j - v[i] >= 0) dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
        }
    }
    cout << dp[n][V] << endl;

    // 2. 解决第二问，背包恰好装满的最大价值
    memset(dp, 0, sizeof(dp)); // 清空dp表
    for (int j = 1; j <= V; j++)
        dp[0][j] = -1; // dp表第一行初始化为-1，表示物品为0时，无法恰好装满背包容量j
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= V; j++)
        {
            dp[i][j] = dp[i - 1][j];
            // 与第一问一致，但需要在加上一个条件判断dp[i-1][j-v[i]]是否是存在能恰好装满的
            if (j - v[i] >= 0 && dp[i - 1][j - v[i]] != -1) 
                dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
        }
    }
    // dp表最后一个位置有可能是不能够恰好装满容量为V的背包，需特判一下
    cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;

    return 0;
}