问题描述

假设有 $i$ 种物品，每种数量无限，第 $i$ 种物品质量为$w[i]$，价值为$v[i]$;给定最大承重为V的背包，求可以得到的最大价值。

状态函数及其转移方程

下面直接贴出最终版。

设$f[i][j]$表示考虑前 $i$ 类物品，给定最大承重为 $j$ 的背包可以获得的最大价值，那么有

$$f[i][j]=max\{f[i-1][j],f[i][j-w[i]]+v[i]\}$$

疑难解释

$f[i-1][j]$表示根本不取第 $i$ 种物品，这不难理解。难点在于对$f[i][j-w[i]]+v[i]$的理解。为什么只腾出了一个$w[i]$的空间？每种数量不是无限的吗？

仍然采用在01背包使用过的优先思想和整体思想。考虑状态$f[i][j]$，它表示考虑前 $i$ 种物品的情况下，背包容量为 $j$ 时所能获得的最大价值。解决这个问题，先决策是否放入第 $i$ 种物品。在考虑放入的情况时，就先放一件，然后把剩余的事情交给 $f[i][j-w[i]]$ 解决，因为它表示的是考虑第 $i$ 件物品时，背包容量 $j-w[i]$的最优解。至于 $f[i][j-w[i]]$ 这个状态中到底有没有/有几件 $i$ 号物品，状态 $f[i][j]$ 并不关心。

归根结底，$f[i][j]$ 的意思是允许放入前 $i$ 种物品。那么状态 $f[i][j-w[i]]$ 所表示的，就是“允许放前 $i$ 种物品，但是削减了一部分空间用来保证第 $i$ 种物品一定入选至少一件，在这种情况下求剩余空间利用的最佳方法”。

总结

无论是01背包，还是完全背包，它们的核心思想都是不变的。即：顺序地考虑物品，但并不是顺序地放入物品。他们都是依次考虑前 $1,2,\dots ,i-1,i$ 种物品，但是对于每一个具体的状态，先决策要不要放入最后一件（种）编号为 $i$ 的再说。

考虑背包问题，一定不能想象成动态的加物品的过程，而是应该对每一个状态都完整地“往空背包里放物品”。所谓“整体考虑”是也。

Last modified on 2020-05-14