Backpack
背包问题可以延展出上十道题目，这里有个博客对这类型题的理解很有帮助：背包九讲
lintcode现在一共有背包系列五道题
这道其实并不是传统上的背包原题，它求的是背包在m的情况下最多可以装多满，不过这仍然跟装更多价值其实是一个意思，只要把物品大小的数组同时也看做物品的价值也就是性价比永远是一比一即可，所以思路上也就跟背包原题一样了，lintcode里面Python的代码过不了，下面是Java代码
public class Solution {
/**
* @param m: An integer m denotes the size of a backpack
* @param A: Given n items with size A[i]
* @return: The maximum size
*/
public int backPack(int m, int[] A) {
// write your code here
int n = A.length;
if (n == 0) {
return 0;
}
int[][] ref = new int[2][m + 1];
for (int i = 0; i < 2; i++) {
for (int j = 0; j < m + 1; j++) {
if (i == 0) {
if (j >= A[0]) {
ref[i][j] = A[0];
} else{
ref[i][j] = 0;
}
} else {
ref[i][j] = 0;
}
}
}
for (int i = 1; i < n; i++) {
for (int j = 0; j < m + 1; j++) {
if (j >= A[i]) {
ref[i % 2][j] = Math.max(ref[(i + 1) % 2][j - A[i]] + A[i], ref[(i + 1) % 2][j]);
} else {
ref[i % 2][j] = ref[(i + 1) % 2][j];
}
}
}
int result = 0;
for (int i = 0; i < 2; i++) {
for (int j = 0; j < m + 1; j++) {
result = Math.max(result, ref[i][j]);
}
}
return result;
}
}
这道才是传统意义上的背包问题，即体积和对应价值的性价比是不一样的，每个物品也只能取一次或者不取，这样可以看出状态方程如下
if j >= weight[i]
dp[i][j] = max(dp[i - 1][j - W[i]] + V[i], dp[i - 1][j])
else
dp[i][j] = dp[i - 1][j]
另外背包问题的一个共性是横纵轴一般一个是数组长度，一个是背包大小
下面是代码
class Solution:
# @param m: An integer m denotes the size of a backpack
# @param A & V: Given n items with size A[i] and value V[i]
# @return: The maximum value
def backPackII(self, m, A, V):
# write your code here
n = len(A)
res = [([0] * (m + 1)) for _ in range(n)]
for i in range(m + 1):
if i >= A[0]:
res[0][i] = V[0]
for i in range(1, n):
for j in range(m + 1):
if j >= A[i]:
res[i][j] = max(res[i - 1][j - A[i]] + V[i], res[i - 1][j])
else:
res[i][j] = res[i - 1][j]
return res[n - 1][m]
下面是一种常见的极限优化空间的写法，因为一般的滚动数组是优化到有两排，但是这里根据背包问题的特性，我们把空间优化到了一排即O(m)而非O(2m)，这种空间优化的规律不太好说明，可以根据画图观察每一个结果的来源来进行优化
class Solution:
# @param m: An integer m denotes the size of a backpack
# @param A & V: Given n items with size A[i] and value V[i]
# @return: The maximum value
def backPackII(self, cap, w, v):
# write your code here
n = len(w)
dp = [0] * (cap + 1)
for i in xrange(cap + 1):
dp[i] = v[0] if i >= w[0] else 0
for i in xrange(1, n):
for j in xrange(cap, -1, -1):
if j >= w[i]:
dp[j] = max(dp[j - w[i]] + v[i], dp[j])
return dp[cap]
这道也是第二题的经典变体即物品可以取用多次，初看好像需要多一层循环在上层所有大于W[i]的下标里找最大值，但是实际上这里运用了一个和正则表达式还有通配符匹配里对*号的多次匹配处理一样的技巧即如果找无限次则我们可以不把dp[i][j]里面的i下标减一，这样dp[i][j - W[i]]即代表了W[i]被选择了多次，道理也很容易想通，即重量减了W[i]而可选物品还是i个，这就可以W[i]被选择了多次，下面是状态方程
if j >= weigth[i]:
dp[i][j] = max(dp[i][j - weight[i]] + value[i], dp[i - 1][j - weight[i]] + value[i], dp[i - 1][j])
else
dp[i][j] = dp[i - 1][j]
上面的三个分别代表选N次，选一次和不选，下面是代码
class Solution:
# @param {int[]} A an integer array
# @param {int[]} V an integer array
# @param {int} m an integer
# @return {int} an array
def backPackIII(self, A, V, m):
# Write your code here
n = len(A)
if not n:
return 0
dp = [([0] * (m + 1)) for _ in xrange(n)]
for i in xrange(m + 1):
dp[0][i] = dp[0][i - A[0]] + V[0] if i >= A[0] else 0
for i in xrange(1, n):
for j in xrange(m + 1):
if j >= A[i]:
dp[i][j] = max(dp[i][j - A[i]] + V[i], dp[i - 1][j - A[i]] + V[i], dp[i - 1][j])
else:
dp[i][j] = dp[i - 1][j]
return dp[n - 1][m]
这道题开始就已经跟之前三道的目的完全不一样了，在这里追求的是把整个背包装满的所有可能性，而所有物品是可以选择无限次的，所以状态方程为
if j >= weight[i]
dp[i][j] = dp[i][j - weight[i]] + dp[i - 1][j] // 其实不懂这一行为什么是这样
else
dp[i][j] = dp[i - 1][j]
这道题还有一个难点是对于状态初始化的定义，对于背包容量为0的情况，我们定义总方案数为1，因为不拿任何东西也是方案的一种，这样根据上面的状态方程，代码如下
class Solution:
# @param {int[]} nums an integer array and all positive numbers, no duplicates
# @param {int} target an integer
# @return {int} an integer
def backPackIV(self, nums, target):
# Write your code here
n = len(nums)
if not n:
return 0
dp = [([0] * (target + 1)) for _ in xrange(n)]
for i in xrange(n):
dp[i][0] = 1
for i in xrange(1, target + 1):
dp[0][i] = dp[0][i - nums[0]] if i >= nums[0] else 0
for i in xrange(1, n):
for j in xrange(1, target + 1):
if j >= nums[i]:
dp[i][j] = dp[i][j - nums[i]] + dp[i - 1][j]
else:
dp[i][j] = dp[i - 1][j]
return dp[n - 1][target]
这道题其实是第四题的简化版，逻辑上比第四题好理解多了，因为每个物品只能选一次，状态方程就跟第二题是一样的了
if j >= nums[i]
dp[i][j] = dp[i - 1][j - nums[i]] + dp[i - 1][j]
else
dp[i][j] = dp[i - 1][j]
另外状态的初始化和第四题一样，不选是一种方案，另外lintcode case太变态了，这里用了滚动数组的优化空间方案，代码是Java写的，Python版本过不去日了狗了_(:зゝ∠)_
public class Solution {
/**
* @param nums an integer array and all positive numbers
* @param target an integer
* @return an integer
*/
public int backPackV(int[] nums, int target) {
// Write your code here
int n = nums.length;
if (n == 0 || nums == null) {
return 0;
}
int[][] dp = new int[2][target + 1];
dp[0][0] = 1;
if (nums[0] <= target) {
dp[0][nums[0]] = 1;
} else {
dp[0][nums[0]] = 0;
}
for (int i = 1; i < n; i++) {
dp[i % 2][0] = 1;
for (int j = 1; j < target + 1; j++) {
if (j >= nums[i]) {
dp[i % 2][j] = dp[(i + 1) % 2][j - nums[i]] + dp[(i + 1) % 2][j];
} else {
dp[i % 2][j] = dp[(i + 1) % 2][j];
}
}
}
return dp[(n + 1) % 2][target];
}
}
这题说实话个人感觉已经不是背包问题了，LeetCode好像有一道combination sum和这个差不多，解题的思路我觉得已经很接近LIS了或者说coin change那道题了，也就是说在当前dp[i]状态下的可行解是所有nums数组里比i小的元素即∑dp[i - num]，所以状态方程如下
dp[i] = ∑dp[i - num] where num is element in nums and num <= i
另外这道题为了节省时间，可以先将nums数组排序再进行DP，下面是代码
class Solution:
# @param {int[]} nums an integer array and all positive numbers, no duplicates
# @param {int} target an integer
# @return {int} an integer
def backPackVI(self, nums, target):
# Write your code here
nums.sort()
dp = [0] * (target + 1)
dp[0] = 1
for i in xrange(1, target + 1):
for num in nums:
if num > i:
break
dp[i] += dp[i - num]
return dp[target]