algo-aha

背包问题：f[v]记录背包容量剩余v时的最大价值。

提炼01背包和完全背包的子过程，用物品（代价c价值w）更新各容量的f[v]。

zeroOnePack(f, c, w):
    for v in V..c  // 逆序遍历各容量
        f[v] = max( f[v], f[v-c]+w )

completePack(f, c, w):
    for v in c..V // 顺序遍历各容量
        f[v] = max( f[v], f[v-c]+w )

不管正序还是逆序，右边的f[v]肯定是f[i-1][v]。01背包和完全背包都在考虑放不放第i个物品，01背包的f[v-c]是旧状态f[i-1][v-c]，逆序保证v维左边是旧状态。完全背包在考虑第i个物品时不管这个物品放没放入过，所以完全背包的f[v-c]是新状态f[i][v-c]，正序保证v维左边是新状态。

初始值：初始的f[]就是在没有放入任何物品时背包的合法状态。如果要求“恰好“装满背包，则f[0]=0其他f[1..V]=-∞；如果没要求恰好装满，则f[0..V]=0。

多重背包：或者某物品多得可当作完全背包问题，或者可把原物品分堆成1,2,4...等重量翻倍的物品 和 剩余重量>0的一个物品，这样就变成多个01背包问题。

multiplePack(f, c, w, m):
    if (cm >= V)
        completePack(f, c, w)
        return
    k = 1
    while (k < m) // <号保证剩余重量>0
        zeroOnePack(f, kc, kw);
        m -= k;
        k *= 2;
    zeroOnePack(f, mc, mw);

二维费用的背包问题：像背包空间v作费用那样，多加一维u作费用，就变成 f[v,u]。对于u同样地，01背包逆序循环，完全背包正序循环。比如限制物品总个数，相当于多了一维件数费用，每个物品的件数费用为1。

分组的背包问题：分为K组，每组最多选一件。设f[k, v]表示前k组物品、容量剩余v时的最大价值，第k组的策略是不选或组中选一件，f[k,v] = max{ f[k-1,v], f[k-1, v-ci] + wi | item i ∈ group k }。代码就是在zeroOnePack()最内层加一层循环在组内选择。

参考：背包问题九讲 https://github.com/tianyicui/pack/blob/master/V2.pdf