完全背包

难度：3星

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

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

• 如果不放，那么等同于前$i-1i-1$个物品，容量为$jj$的背包的最优方案。
• 如果放，又可以分为放1个，2个....k个，同01背包的转移方程, 只不过max中的2项就变成了$k-1k-1$项：

$dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i],dp[i-1][j-2v[i]]+2w[i],\mathrm{.}\mathrm{.}\mathrm{.},dp[i-1][j-kv[i]]+kw[i])dp[i][j]\; =\; max(dp[i-1][j],\; dp[i-1][j-v[i]]+w[i],\; dp[i-1][j-2v[i]]+2w[i],\; ...\; ,\; dp[i-1][j-kv[i]]+kw[i])$

但是这样算的复杂度太高了，我们对上面式子进行变形。

用$j-v[i]j-v[i]$带入上式的$jj$, 去掉最后一项（因为$j-kv[i]j-kv[i]$已经小于$v[i]v[i]$，不能再减。) 得：

$dp[i][j-v[i]]=max(dp[i-1][j-v[i]],dp[i-1][j-2v[i]]+w[i],\mathrm{.}\mathrm{.}\mathrm{.}dp[i-1][j-kv[i]]+(k-1)w[i])dp[i][j-v[i]]\; =\; max(dp[i-1][j-v[i]],\; dp[i-1][j-2v[i]]+w[i],\; ...\; dp[i-1][j-kv[i]]+(k-1)w[i])$

发现这个式子加上$w[i]w[i]$正好是上式的后$kk$项，代替之：

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

同样的，发现还是可以进行压缩，只不过为了先覆盖掉$j-v[i]j-v[i]$项，我们必须正向计算。

本题也有两个问，思路与01背包完全相同。

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[i]; j <= V; 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[i]; j <= V; 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;
}