01背包

难度：3星

设 $dp[i][j]dp[i][j]$ 为前$ii$个物品，背包容量为$jj$的最大价值。

那么考虑第$ii$个物品是否放入，有两种情况：

• 如果不放，那么等同于前$i-1i-1$个物品，容量为$jj$的背包的最优方案。
• 如果放，那么等同于前$i-1i-1$个物品，容量为$j-v[i]j-v[i]$的背包的最优方案，再加上第$ii$个物品的价值。

那么可以得到转移方程：

$dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]dp[i][j]\; =\; max(dp[i-1][j],\; dp[i-1][j-v[i]]+w[i]$

最终的答案就是$dp[n][V]dp[n][V]$.

观察到本题的$dpdp$数组，第$ii$行仅跟上一行有关系，故可以压缩一维，而且为了防止$dp[i-1][j-v[i]]dp[i-1][j-v[i]]$被覆盖掉，第二维度必须反向枚举。

另外本题有2个问，区别在于初值如何取。

1. 如果不要求背包恰好装满，则无论如何都可以不放，因此数组初始化为0.
2. 如果要求背包恰好装满，则初始化为最大价值的最小值，即$-INF-INF$, 这样如果上一层$j-v[i]j-v[i]$的背包没装满，下一层还是装不满，$-INF+w[i]-INF+w[i]$仍为一个很小的负数。同时背包容量为0时，恰好装满等价于什么也不装，因此同时初始化$dp[0]=0dp[0]=0$.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1010;
const int INF = 0x3f3f3f3f;

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

int main()
{
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false), cin.tie(0);

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

    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; i++)
        for (int j = V; j >= v[i]; j--)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);

    cout << dp[V] << endl;

    memset(dp, -0x3f, sizeof(dp));
    dp[0] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = V; j >= v[i]; j--)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);

    if (dp[V] < 0) dp[V] = 0;
    cout << dp[V] << endl;
    return 0;
}