主要介绍 0-1 背包问题, 及一些 leetcode 题解
0-1 背包问题
定义
有一个背包, 他的容量为 C(Capacity). 现在有 n 中不同的物品, 编号为 0...n-1, 其中每一件物品的重量为 w(i), 价值为 v(i). 问可以向这个背包中盛放哪些物品, 使得在不超过背包容量的基础上, 物品的总价值最大.
解题思路
这类组合问题, 我们都可以使用递归来完成. 只是我们在其中能不能找到重叠子问题, 最优子结构进而转化成记忆化搜索或动态规划来解决.
对于这个问题, 我们有两个约束条件
首先我们要在 n 个物品里选
第二点他的容量要小于等于一个给定的数值 C.
状态定义
注意这个问题要使用两个变量来定义状态.
F(n,C)考虑将 n 个物品放进容量为 C 的背包, 使得价值最大.
状态转移
对于 F(i,c), 有两种情况, 将第 i 个物品加入和直接忽略第 i 个物品
F(i,C) = max{F(i-1, C), v(i) + F(i-1, C-w(i))}
代码实现
记忆化搜索法
- class Knapsack01{
- private:
- vector<vector<int>> memo;
- // 用 [0...index]的物品, 填充容积为 c 的背包的最大价值
- int bestValue(const vector<int> &w, const vector<int> v, int index, int c){
- if( c <= 0 || index <0 ) {
- return 0;
- }
- if( memo[index][c] != -1 ) {
- return memo[index][c];
- }
- int res = bestValue(w, v, index-1, c);
- if( c>= w[index] ) {
- res = max( res , v[index] + bestValue(w, v, index-1, c-w[index]) );
- }
- memo[index][c] = res;
- return res;
- }
- public:
- int knapsack01(const vector<int> &w, const vector<int> &v, int C){
- assert( w.size() == v.size() && C>= 0 );
- int n = w.size();
- if( n == 0 || C == 0 )
- return 0;
- memo = vector<vector<int>>( n, vector<int>(C+1,-1));
- return bestValue(w, v, n-1, C);
- }
- };
使用动态规划自底向上解决
模拟一下, 每个位置都由两个位置决定
https://user-gold-cdn.xitu.io/2018/7/7/1647513f97bdf4c2?w=746&h=301&f=png&s=68700
- class Knapsack01{
- public:
- // 用 [0...index]的物品, 填充容积为 c 的背包的最大价值
- int knapsack01(const vector<int> &w, const vector<int> &v, int C){
- assert( w.size() == v.size() && C>= 0 );
- if ( n == 0) {
- return 0;
- }
- int n = w.size();
- vector<vector<int>> memo( n, vector<int>(C+1,0));
- for ( int j = 0; j <= C; j++ ) {
- memo[0][j] = ( j>= w[0] ? v[0] : 0 );
- }
- for ( int i = 1; i <n; i++ ) {
- for ( int j = 0; j <= C; j++ ) {
- // 0~i 这些物品容积为 j 的背包获得的最大值
- memo[i][j] = memo[i-1][j];
- if( j>= w[i] ) {
- memo[i][j] = max( memo[i][j], v[i] + memo[i-1][j-w[i]]);
- }
- }
- }
- return memo[n-1][C];
- }
- };
0-1 背包问题优化
分析
上面的 0-1 背包问题的时间复杂度: O(nC), 空间复杂度: O(nC).
我们分析一下状态转移方程: F(i,C) = max{F(i-1, C), v(i) + F(i-1, C-w(i))}
第 i 行元素只依赖于第 i-1 行元素. 理论上, 只需要保持两行元素. 空间复杂度: O(2*C)=O(C).
两行轮流使用完成背包问题
- class Knapsack01{
- public:
- int knapsack01(const vector<int> &w, const vector<int> &v, int C){
- assert( w.size() == v.size() && C>= 0 );
- int n = w.size();
- if( n == 0 && C == 0 )
- return 0;
- vector<vector<int>> memo( 2, vector<int>(C+1,0));
- for( int j = 0 ; j <= C ; j ++ )
- memo[0][j] = ( j>= w[0] ? v[0] : 0 );
- for( int i = 1 ; i <n ; i ++ )
- for( int j = 0 ; j <= C ; j ++ ){
- memo[i%2][j] = memo[(i-1)%2][j];
- if( j>= w[i] )
- memo[i%2][j] = max( memo[i%2][j], v[i] + memo[(i-1)%2][j-w[i]]);
- }
- return memo[(n-1)%2][C];
- }
- };
继续优化
只使用一行完成背包问题, 比较复杂: 我们从右向左刷新内容
https://user-gold-cdn.xitu.io/2018/7/7/1647513f94786e8c?w=754&h=328&f=png&s=48690
代码实现
- class Knapsack01{
- public:
- int knapsack01(const vector<int> &w, const vector<int> &v, int C){
- assert( w.size() == v.size() && C>= 0 );
- int n = w.size();
- if( n == 0 || C == 0 )
- return 0;
- vector<int> memo(C+1,0);
- for( int j = 0 ; j <= C ; j ++ )
- memo[j] = ( j>= w[0] ? v[0] : 0 );
- for( int i = 1 ; i <n ; i ++ )
- for( int j = C ; j>= w[i] ; j -- )
- memo[j] = max( memo[j], v[i] + memo[j-w[i]]);
- return memo[C];
- }
- };
0-1 背包问题变种
多重背包问题: 每个物品不止 1 个, 有 num(i)个
完全背包问题: 每个物品可以无限使用
多维费用背包问题: 要考虑物品的体积和重量两个维度
物品间加入更多约束: 物品间可以相互排斥; 也可以相互依赖
面试中的 0-1 背包问题
leetcode 416. 分割等和子集
分析
典型的背包问题, 在 n 个物品中选出一定物品, 填满 sum/2 的背包.
记忆化搜索法
- class Solution {
- private:
- // memo[i][c] 表示使用索引为 [0...i] 的这些元素, 是否可以完全填充一个容量为 c 的背包
- // -1 表示为未计算; 0 表示不可以填充; 1 表示可以填充
- vector<vector<int>> memo;
- // 使用 nums[0...index], 是否可以完全填充一个容量为 sum 的背包
- bool tryPartition(const vector<int> &nums, int index, int sum){
- if( sum == 0 ) {
- return true;
- }
- if( sum <0 || index < 0 ) {
- return false;
- }
- if( memo[index][sum] != -1 ) {
- return memo[index][sum] == 1;
- }
- memo[index][sum] = (tryPartition(nums, index-1 , sum ) ||
- tryPartition(nums, index-1 , sum - nums[index] ) ) ? 1 : 0;
- return memo[index][sum] == 1;
- }
- public:
- bool canPartition(vector<int>& nums) {
- int sum = 0;
- for( int i = 0 ; i <nums.size() ; i ++ ){
- assert( nums[i]> 0 );
- sum += nums[i];
- }
- if( sum%2 ) {
- return false;
- }
- memo = vector<vector<int>>(nums.size(), vector<int>(sum/2+1,-1));
- return tryPartition(nums, nums.size()-1 , sum/2 );
- }
- };
自底向上使用动态规划
- class Solution {
- public:
- bool canPartition(vector<int>& nums) {
- int sum = 0;
- for( int i = 0 ; i <nums.size() ; i ++ ){
- assert( nums[i]> 0 );
- sum += nums[i];
- }
- if( sum%2 ) {
- return false;
- }
- int n = nums.size();
- int C = sum / 2;
- vector<bool> memo(C+1, false);
- for ( int i = 0; i <= C; i++ ) {
- memo[i] = ( nums[0] == i );
- }
- for ( int i = 1; i <n; i++ ) {
- for ( int j = C; j>= nums[i]; j-- ) {
- memo[j] = memo[j] || memo[ j - nums[i] ];
- }
- }
- return memo[C];
- }
- };
相似问题
- leetcode 322
- leetcode 377
- leetcode 474
- leetcode 139
- leetcode 494
来源: https://juejin.im/post/5b40c99ee51d45190b615f33