0-1 背包问题
给你一个可装载重量为W
的背包和N
个物品,每个物品有重量和价值两个属性。其中第i
个物品的重量为wt[i]
,价值为val[i]
,现在让你用这个背包装物品,最多能装的价值是多少?(这个题目中的物品不可以分割,要么装进包里,要么不装,不能说切成两块装一半。这也许就是 0-1 背包这个名词的来历。)
标准套路
第一步 ** **要明确两点,「状态」和「选择」。
先说状态,如何才能描述一个问题局面?只要给定几个可选物品和一个背包的容量限制,就形成了一个背包问题,对不对?所以状态有两个,就是「背包的容量」和「可选择的物品」。
对于每件物品选择就是「装进背包」或者「不装进背包」嘛。
明白了状态和选择,动态规划问题基本上就解决了,只要往这个框架套就完事儿了:
for 状态1 in 状态1的所有取值:
for 状态2 in 状态2的所有取值:
for ...
dp[状态1][状态2][...] = 择优(选择1,选择2...)
第二步 要明确 dp
数组的定义。
dp
数组是什么?其实就是描述问题局面的一个数组。换句话说,我们刚才明确问题有什么「状态」,现在需要用dp
数组把状态表示出来
dp[i][w]
的定义如下:对于前i
个物品,当前背包的容量为w
,这种情况下可以装的最大价值是dp[i][w]
。
根据这个定义,我们想求的最终答案就是dp[N][W]
。base case 就是dp[0][..] = dp[..][0] = 0
**,因为没有物品或者背包没有空间的时候,能装的最大价值就是 0。
细化上面的框架:
int dp[N+1][W+1]
dp[0][..] = 0
dp[..][0] = 0
for i in [1..N]:
for w in [1..W]:
dp[i][w] = max(
把物品 i 装进背包,
不把物品 i 装进背包
)
return dp[N][W]
第三步 ,根据「选择」,思考状态转移的逻辑。
简单说就是,上面伪码中「把物品i
装进背包」和「不把物品i
装进背包」怎么用代码体现出来呢?
这一步要结合对dp
数组的定义和我们的算法逻辑来分析:
如果你没有把这第 i
个物品装入背包,那么很显然,最大价值dp[i][w]
应该等于dp[i-1][w]
。你不装嘛,那就继承之前的结果。
如果你把这第 i
个物品装入了背包,那么dp[i][w]
应该等于dp[i-1][w-wt[i-1]] + val[i-1]
。
进一步细化代码:
for i in [1..N]:
for w in [1..W]:
dp[i][w] = max(
dp[i-1][w],
dp[i-1][w - wt[i-1]] + val[i-1]
)
return dp[N][W]
最后一步 把伪码翻译成代码,处理一些边界情况。
处理了w - wt[i-1]
可能小于 0 导致数组索引越界的问题:
int knapsack(int W, int N, vector<int>& wt, vector<int>& val) {
// vector 全填入 0,base case 已初始化
vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0));
for (int i = 1; i <= N; i++) {
for (int w = 1; w <= W; w++) {
if (w - wt[i-1] < 0) {
// 当前背包容量装不下,只能选择不装入背包
dp[i][w] = dp[i - 1][w];
} else {
// 装入或者不装入背包,择优
dp[i][w] = max(dp[i - 1][w - wt[i-1]] + val[i-1],
dp[i - 1][w]);
}
}
}
return dp[N][W];
}
子集背包问题
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
分析:
可以先对集合求和,得出sum
,把问题转化为背包问题:
给一个可装载重量为sum/2
的背包和N
个物品,每个物品的重量为nums[i]
。现在让你装物品,是否存在一种装法,能够恰好将背包装满?
第一步要明确两点,「状态」和「选择」。
这个前文 [0-1背包问题]已经详细解释过了,状态就是「背包的容量」和「可选择的物品」,选择就是「装进背包」或者「不装进背包」。
第二步要明确dp
数组的定义。
按照背包问题的套路,可以给出如下定义:
dp[i][j] = x
表示,对于前i
个物品,当前背包的容量为j
时,若x
为true
,则说明可以恰好将背包装满,若x
为false
,则说明不能恰好将背包装满。
根据这个定义,我们想求的最终答案就是dp[N][sum/2]
,base case 就是dp[..][0] = true
和dp[0][..] = false
,因为背包没有空间的时候,就相当于装满了,而当没有物品可选择的时候,肯定没办法装满背包
第三步,根据「选择」,思考状态转移的逻辑。
回想刚才的dp
数组含义,可以根据「选择」对dp[i][j]
得到以下状态转移:
如果不把nums[i]
算入子集,或者说你不把这第i
个物品装入背包,那么是否能够恰好装满背包,取决于上一个状态dp[i-1][j]
,继承之前的结果。
如果把nums[i]
算入子集,或者说你把这第i
个物品装入了背包,那么是否能够恰好装满背包,取决于状态dp[i - 1][j-nums[i-1]]
。
最后一步,把伪码翻译成代码,处理一些边界情况。
bool canPartition(vector<int>& nums) {
int sum = 0;
for (int num : nums) sum += num;
// 和为奇数时,不可能划分成两个和相等的集合
if (sum % 2 != 0) return false;
int n = nums.size();
sum = sum / 2;
vector<vector<bool>> dp(n + 1, vector<bool>(sum + 1, false));
// base case
for (int i = 0; i <= n; i++)
dp[i][0] = true;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= sum; j++) {
if (j - nums[i - 1] < 0) {
// 背包容量不足,不能装入第 i 个物品
dp[i][j] = dp[i - 1][j];
} else {
// 装入或不装入背包
dp[i][j] = dp[i - 1][j] | dp[i - 1][j-nums[i-1]];
}
}
}
return dp[n][sum];
}
状态压缩:
注意到dp[i][j]
都是通过上一行dp[i-1][..]
转移过来的,之前的数据都不会再使用了。
所以,我们可以进行状态压缩,将二维dp
数组压缩为一维,节约空间复杂度:
bool canPartition(vector<int>& nums) {
int sum = 0, n = nums.size();
for (int num : nums) sum += num;
if (sum % 2 != 0) return false;
sum = sum / 2;
vector<bool> dp(sum + 1, false);
// base case
dp[0] = true;
for (int i = 0; i < n; i++)
for (int j = sum; j >= 0; j--)
if (j - nums[i] >= 0)
dp[j] = dp[j] || dp[j - nums[i]];
return dp[sum];
}
唯一需要注意的是j
应该从后往前反向遍历,因为每个物品(或者说数字)只能用一次,以免之前的结果影响其他的结果。
完全背包问题(物品数量无限)
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个
分析:
把这个问题转化为背包问题的描述形式:
有一个背包,最大容量为amount
,有一系列物品coins
,每个物品的重量为coins[i]
,每个物品的数量无限。请问有多少种方法,能够把背包恰好装满?
第一步要明确两点,「状态」和「选择」。
状态有两个,就是「背包的容量」和「可选择的物品」,选择就是「装进背包」或者「不装进背包」。
第二步要明确 dp
数组的定义。
dp[i][j]
的定义如下:
若只使用前i
个物品,当背包容量为j
时,有dp[i][j]
种方法可以装满背包。
base case 为dp[0][..] = 0, dp[..][0] = 1
。因为如果不使用任何硬币面值,就无法凑出任何金额;如果凑出的目标金额为 0,那么“无为而治”就是唯一的一种凑法。
第三步,根据「选择」,思考状态转移的逻辑。
如果你不把这第i
个物品装入背包,也就是说你不使用coins[i]
这个面值的硬币,那么凑出面额j
的方法数dp[i][j]
应该等于dp[i-1][j]
,继承之前的结果。
如果你把这第i
个物品装入了背包,也就是说你使用coins[i]
这个面值的硬币,那么dp[i][j]
应该等于dp[i][j-coins[i-1]]
。
最后一步,把伪码翻译成代码,处理一些边界情况。
我用 Java 写的代码,把上面的思路完全翻译了一遍,并且处理了一些边界问题:
int change(int amount, int[] coins) {
int n = coins.length;
int[][] dp = amount int[n + 1][amount + 1];
// base case
for (int i = 0; i <= n; i++)
dp[i][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= amount; j++)
if (j - coins[i-1] >= 0)
dp[i][j] = dp[i - 1][j]
+ dp[i][j - coins[i-1]];
else
dp[i][j] = dp[i - 1][j];
}
return dp[n][amount];
}
通过观察可以发现,dp
数组的转移只和dp[i][..]
和dp[i-1][..]
有关,所以可以压缩状态,进一步降低算法的空间复杂度:
int change(int amount, int[] coins) {
int n = coins.length;
int[] dp = new int[amount + 1];
dp[0] = 1; // base case
for (int i = 0; i < n; i++)
for (int j = 1; j <= amount; j++)
if (j - coins[i] >= 0)
dp[j] = dp[j] + dp[j-coins[i]];
return dp[amount];
}
这个解法和之前的思路完全相同,将二维dp
数组压缩为一维,时间复杂度 O(N*amount),空间复杂度 O(amount)。