背包问题

看到从给定的一堆items按序选取几个(针对每个j <V, 每个item只选择一次)使他们的某个数量加起来的和最大(<V)或最小或刚好等于V，则想到0-1背包。

如果一件物品能选择无数次，则是完全背包，如322 Coin Change。

0-1背包的套路: 从nums[]中选，每个元素能选一次，求能刚好满足和为V的子集的最短长度。

int f[][] = new int[n + 1][V + 1]; // 前i个元素凑成的子集和为j最短长度。
f[0][0] = 0; // 不用选任何元素即满足，长度0
for (int i = 1; i <= n; i++) {
    f[i][0] = Integer.MAX_VALUE;
}
for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= V; j++) {
        f[i][j] = f[i - 1][j]; // 默认不选物品i
        if (j - nums[i] >= 0 && f[i - 1][j - nums[i]] != Integer.MAX_VALUE) {
            // 与选择i时能达到的长度比较，选择了i意味着用前i-1个物品装满j - nums[i]
            f[i][j] = Math.min(f[i][j], f[i - 1, j - nums[i]] + 1); 
        }
    }
}

return f[n][V];

我们可以看到，f[i][]的状态只与f[i-1]有关，因此我们可以用一维数组优化空间。

int f[] = new int[V + 1];
f[0] = 0;
for (int i = 1; i <= V; i++) {
    f[i] = Integer.MAX_VALUE;
}
for (int i = 0; i < n; i++) {
    // 这里要倒着来，因为在开始前f里相当于存着f[i-1][]
    for (int j = V; j >= nums[i]; j--) { 
        if (f[j - nums[i]] != Integer.MAX_VALUE) {
            f[j] = Math.min(f[j], f[j - nums[i]] + 1);
        }
    }
}

 return f[V];

完全背包: 从nums[]中选，每个元素能选无限次，求能刚好满足和为V的子集的最短长度。

int f[] = new int[V + 1];
f[0] = 0;
for (int i = 1; i <= V; i++) {
    f[i] = Integer.MAX_VALUE;
}
for (int i = 0; i < n; i++) {
    // 这里要正着来，因为f[i][j] = min(f[i - 1][j], f[i][j - k * nums[i]] + 1 | k = 1,2,...,V/nums[i])
    // 当转成一维，0-1背包倒着来是“为了保证每件物品只选择一次，在考虑i时依赖绝不包含i的子结果f[i-1,j-nums[i]]
    // 而现在恰是每件物品可以选择无数次，正需要一个可能已选入i的子结果f[i][j-nums[i]]
    // 因此f[i][j] = min(f[i-1][j],f[i][j-nums[i]] + 1),
    // 其中f[i][j-nums[i]]又可以展开成与j - 2 * nums[i]相关的, 依次类推直到j - V/nums[i] * nums[i] 
    // 所以在j循环开始前f[j]初始值即f[i-1][j], 当j增加时相当于从j-V/nums[i]*nums[i]从底往前递推。
    for (int j = nums[i]; j <= V; j++) { 
        if (f[j - nums[i]] != Integer.MAX_VALUE) {
            f[j] = Math.min(f[j], f[j - nums[i]] + 1);
        }
    }
}

 return f[V];

有些题看上去像背包问题，但实际上不方便套用。比如Combination Sum IV。因为背包问题的解本质上是combination而不是permutation。如果选的物品顺序也有关系则无法直接使用背包模板。

关于状态转移方程, 当求how many ways时f[j] += f[j - nums[i]], 当问求能刚好满足和为V的子集的最短长度f[j] = Math.min(f[j], f[j - nums[i]] + 1);