0-1背包及其变种

嘛，每次遇到0/1背包都忘得一干二净。

最朴素的0/1背包：有N件物品和一个容量V的背包。第i件物品的费用是c[i]，价值是w[i]。问怎么挑选物品使得背包价值最大。

记f[i][v]表示前i件物品装入容量v的背包的最大价值。那么，状态转移方程：

f[i][v] = max{ f[i-1][v], f[i-1][v-c[i]]+w[i] }

• f[i-1][v]表示：不选择第i件物品，问题转化为前i-1件物品装入容量v的背包的最大价值。
• f[i-1][v-c[i]]表示：选择第i件物品，问题转化为前i件物品装入容量v-c[i]的背包的最大价值。

伪代码算法

for i=1...N
    for v=0...V
        f[i][v] = max{ f[i-1][v], f[i-1][v-c[i]]+w[i] }
print f[N][V]

0/1背包可以优化空间复杂度。因为f[i][v]由f[i-1][v], f[i-1][v-c[i]]两个子问题递推而来，而且f[i-1][v], f[i-1][v-c[i]]只会被f[i][v]利用，所以没有必要一直保存f[i][…]值，只需要f[0…V]一维数组保存状态，空间复杂度O(V)。这时候需要保证第i次循环中推f[v]时候，f数组中f[v]和f[v-c[i]]保存的是f[i-1][v], f[i-1][v-c[i]]的值。事实上，每次在主循环中以v=V..0的顺序推f[v]就能保证要求。

for i=1..N
    for v=V..0
        f[v]=max{f[v],f[v-c[i]]+w[i]};

0/1背包问题的变种

leetcode 416

给定一个集合nums，问能够将一个集合拆分为两个集合，两个集合的元素和相等。

问题等价于选取一定数目元素，使得选择的元素之和为sum/2。进一步转化为0/1背包问题，给定一个正整数数组，从数组中选取一定数量元素，使得元素之和恰好为sum/2。

假设f[i][j]表示数组前i个元素能够得到和为j的子数组：1表示能，0表示不能。那么状态转移方程：

f[i][j] = f[i-1][j] 或 f[i-1][j-nums[i]]

for (int i = 0; i < n; i++) {
    f[i][0] = 1;
}
//f[0][nums[0]] = 1; 多此一举
for (int i = 0; i < n; i++) {
    for (int j = 0; j <= sum / 2; j++) {
        if (j - nums[i] >= 0 && i - 1 >= 0) {
            f[i][j] = f[i-1][j] | f[i-1][j-nums[i]];
        }
    }
}
return f[n-1][sum/2];

空间压缩

int f[20005];
f[0] = 1;
for (int i = 0; i < n; i++) {
    //f[nums[i]] = 1; 多次一举，而且错误
    for (int j = sum/2; j >= nums[i]; j--) {
        f[j] = f[j] | f[j-nums[i]];
    }
    //f[nums[i]] = 1; 多次一举，但是正确
}
return f[sum/2];

hiho 1453

这题抓住有n孩子的节点能增加n通块。然后对于k = [1, n]，对所有树节点，是否能达到k-1个增加通块的最小操作数。17年第一道AC，加油。

嘛，以后想不清楚，可以举个例子走一遍流程。0/1背包问题就是给一堆东西，选或者不选，达到某种目标时的最大或者最小状态。