背包DP

在背包$DP$中，我们会看到关于其 体积或质量 上不同的表示，如果将其忽视，从而失误，那无疑是非常遗憾的。

背包DP中的 “质量不超过” 求最大价值

这是背包$DP$中 最常出现 的关键词。

因为求的是 最大价值，所以质量肯定是 越大越好，所以可以直接取不超过要求的最大质量。

for (int i = 1; i <= n; ++ i)
    for (int j = m; j >= v[i]; j -- )
        f[j] = max(f[j], f[j - v[i]] + w[i]);

在上面的状态转移方程中，我们可以看到，增加价值的前提是当前质量大于物品质量，才能保证物品质量不大于要求。

背包DP中的 “恰好”

这种表达最大或最小价值都可以用。

不同点在于，最小值要更新初始状态，且用 $min$, 最大值用 $max$。

最小：

memset(f, 0x3f, sizeof f);
f[0] = 0;

for (int i = 1; i <= n; ++ i)
    for (int j = m; j >= v[i]; j -- )
        f[j] = min(f[j], f[j - v[i] + w[i]);

最大：

for (int i = 1; i <= n; ++ i)
    for (int j = m; j >= v[i]; j -- )
        f[j] = max(f[j], f[j - v[i]] + w[i]);

背包DP中的 “质量不少于” 求最小价值

这种表达主要用于最小价值，其不同点主要在状态转移过程中。

memset(f, 0x3f, sizeof f);
f[0] = 0;

for (int i = 1; i <= n; ++ i)
    for (int j = m; j >= 0; j -- )
        f[j] = min(f[j], f[max(0, j - v[i])] + w[i]);

为什么要这么做呢？

这是因为，物品质量不能低于要求，所以就算大于要求也可以加上去。

注意 $f[0] = 0;$ 这个语句起到了边界作用，因为没有质量的最小价值就是 0

而其中的 $f[j] = min(f[j], f[max(0, j - v[i])] + w[i]);$ 中 $min$ 是在其中找最小，

其中 $f[max(0, j - v[i])]$ 的作用是确保物品质量一直不小于要求，即使当前质量特别小，只要不是 $0$，就一定有价值。