前提：$K, w_i$ 是整数。
数学递归方案
-
表示：$O[k, n]$ 表示在已经携带 $k$ 重量物品，物品集合为 $I \cap[1, n]$ 时的最优目标函数值。
-
起始条件：$\forall k, O[k, 0] = 0$。
-
终止条件：我们的目标是求解出 $\forall k, O[k, N]$，再通过作 $\max_{k=0}^K O[k, N]$ 就是最优解。
-
递归方案：
- 假设我们已经知道了所有的 $\forall k, O[k, n-1]$，我们想要求 $\forall k, O[k, n]$，那么我们只需要多考虑第 $n$ 个物体。对于每个新容量 $k$（注意不是旧容量，见注）：
- 如果 $k < w_n$，这个新容量肯定是不能由放入物体 $n$ 而来的（不然旧容量 $k - w_n$ 是负值），因而 $O[k, n+1] = O[k, n]$。
- 如果 $k \ge w_n$，可以选择这个容量是放物体 $n$ 而来的或者不放物体 $n$ 而来的：
- 如果不放就还是 $O[k, n] = O[k, n-1]$；
- 如果放就是 $O[k, n] = O[k - w_n, n-1] + v_{n}$；
- 要选择这两样物体的最优值，$O[k, n] = \min \{ O[k, n-1], O[k - w_n, n-1] + v_{n} \}$。
注：数学上更倾向于「人人为我」的递归模式，因而以要求解的目标对象为主。如果我们是知道 $n$ 的想要「去求」$n+1$ 的，并认为 $k$ 是旧容量「来去求考虑 $n+1$ 对象后的新容量」，就是这样的「我为人人」模式：
- 假设我们已经知道了 $\forall k, O[k, n]$，想要求 $\forall k, O[k, n+1]$，那么我们只需要多考虑第 $n+1$ 个物体。对于每个放置前的容量 $k$：
- 如果 $k + w_{n+1} > K$，物体肯定放不进去了，因而 $O[k, n+1] = O[k, n]$。
- 如果 $k + w_{n+1} \le K$，可以选择放物体或者不放物体：
- 如果不放物品就还是 $O[k, n+1] = O[k, n]$；
- 如果放物品就是 $O[k+ w_{n+1}, n+1] = O[k, n] + v_{n+1}$；
- 这是一个「我为人人」顺序模式，只要保证登记的总是最大值即可。
- 假设我们已经知道了所有的 $\forall k, O[k, n-1]$，我们想要求 $\forall k, O[k, n]$，那么我们只需要多考虑第 $n$ 个物体。对于每个新容量 $k$（注意不是旧容量，见注）：
Top-down 递归实现：
def O(k, n):
if n == 0:
return 0
elif k < w[n]:
return O(k, n-1)
else:
return max(O(k, n-1), O(k-w[n], n-1) + v[n])
- 显然这个量级和斐波那契数列的递归求解是一样的。
Bottom-up 计算：逐渐建立一个二维表 $O[k, n]$。
Trace-back：如果和左边的数相同，就是没选，如果不同，就是选了。
Complexity：$O(K \cdot N)$
- 但考虑到编码一个容量需要 $\log_2 K$ bits 之类的（?: 这重要吗？），还是会有一些特殊情况。
