svn performance powershell testing events dynamic mono vue前端框架 网络营销视频 bootstrap图表 matlab跳出for循环 matlab区分大小写吗 python获取字典的值 eclipse安装python java开发接口 javarandom java手册 linux服务器 python源码 unix操作系统下载 冬青鼠 如何给黑白照片上色 英雄联盟崩溃 小洛快跑 办公室复印机使用方法 证书小精灵 小米游戏鼠标 bootskin 1500左右性价比最高的手机 ps反选 qq悄悄话怎么知道对方是谁 画图3d 向日葵9 进存销软件 mysql退出命令 搜狗拼音输入法安装包 俄罗斯方块java fleaphp kz文件怎么打开 梦幻西游手游辅助
当前位置: 首页 > 学习教程  > 编程语言

leetcode算法之动态规划(背包问题)

2021/2/13 17:22:26 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

今天来盘一盘 **动态规划(背包问题) ** 这类题目 这是最让我头疼的一类题目,一直不想做这类题目,这里开始学习一下。 使用python刷题分类整理的笔记,请参考: https://github.com/lxztju/leetcode-algorithm/tree/v1 动态规划&a…

今天来盘一盘 **动态规划(背包问题) ** 这类题目

这是最让我头疼的一类题目,一直不想做这类题目,这里开始学习一下。

使用python刷题分类整理的笔记,请参考: https://github.com/lxztju/leetcode-algorithm/tree/v1

动态规划(背包问题)

动规就是以空间换取时间。

0-1背包是背包问题的一个主要的表现形式,在01背包的基础上发展出来的还有完全背包以及多维背包问题。

0-1背包

问题描述为: 存在一个容量为 C 的背包,和N类物品。这些物品分别有两个属性,重量w 和价值 v,每个物品的重量为w[i], 价值为v[i],每种物品只有一个。在不超过背包容量的情况下能够装入最大的价值为多少?(这个背包可以不装满)。

如果采用暴力法,每个物品都有装入与不装入两种情况,复杂度为2的n次幂,复杂度为指数级别的复杂度。如果使用动态规划,时间复杂度会降低至O(N*C)。

dp[i][j] 为将前i件物品装进容量为j的背包可以获得的最大价值, 0<=i<=N, 0<=j<=C

dp表为(N+1)x(C+1)维的二维数组
  • 状态转移方程
1. 不装入第i件物品时,dp[i][j] = dp[i-1][j];
2. 装入第i件物品,dp[i][j] = dp[i-1][ j-w[i] ] + v[i];  (j > w[i] 背包的容量大于w[i])
状态转移方程:
	dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])  
  • base case
第0个物品时不存在的,价值为0。
dp[0][:] = 0;
  • 基本的实现过程:
// 定义dp
vector<vector<int>> dp(N+1, vector<int>(C+1, 0))

// 定义base case
for (int j = 0; j < c+1; j++)
	dp[0][j] = 0;
// 执行状态转移
for (int i = 1; i < N+1; i++){
	for (int j = C; j >= 0; j--){
		dp[i][j] = dp[i-1][j];
		if (j >= w[i])
			dp[i][j]  = max(dp[i][j], dp[i-1][j-w[i]] + v[i]);	
	}
}
return dp[N][C];
  • 优化的实现过程(dp采用一维数组)
初始dp[j]均为0
for (int i = 1; i < N+1; i++){
	for (int j = C; j >= 0; j--){
		if (j >= w[i])
			dp[j]  = max(dp[j], dp[j-w[i]] + v[i]);	
	}
}

完全背包

问题描述为: 存在一个容量为 C 的背包,和N类物品。这些物品分别有两个属性,重量w 和价值 v,每种物品的重量为w[i], 价值为v[i],每种物品有无穷多个。在不超过背包容量的情况下能够装入最大的价值为多少?(这个背包可以不装满)。

dp[i][j] 为将前i件物品装进容量为j的背包可以获得的最大价值, 0<=i<=N, 0<=j<=C

dp表为(N+1)x(C+1)维的二维数组

完全背包与01背包的思路基本一致,只是每种物品可以有无限多个,因此每次装入第i种物品后,还能继续装入i种物品。

  • 状态转移方程
1. 不装入第i种物品时,dp[i][j] = dp[i-1][j];
2. 装入第i件物品,dp[i][j] = dp[i][ j-w[i] ] + v[i];  (j > w[i] 背包的容量大于w[i])
状态转移方程:
	dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]]+v[i])  
  • base case
第0个物品时不存在的,价值为0。
dp[0][:] = 0;
  • 基本的实现过程:
// 定义dp
vector<vector<int>> dp(N+1, vector<int>(C+1, 0))

// 定义base case
for (int j = 0; j < c+1; j++)
	dp[0][j] = 0;
// 执行状态转移
for (int i = 1; i < N+1; i++){
	for (int j = 0; j <=C ; j++){
		dp[i][j] = dp[i-1][j];
		if (j >= w[i])
			dp[i][j]  = max(dp[i][j], dp[i][j-w[i]] + v[i]);	
	}
}
return dp[N][C];
  • 优化的实现过程(dp采用一维数组)
初始dp[j]均为0
for (int i = 1; i < N+1; i++){
	for (int j = 0; j <= C; j++){
		if (j >= w[i])
			dp[j]  = max(dp[j], dp[j-w[i]] + v[i]);	
	}
}

多重背包

问题描述为: 存在一个容量为 C 的背包,和N类物品。这些物品分别有三个属性,重量w ,价值 v和数量n,每种物品的重量为w[i], 价值为v[i],每种物品分别有n[i]个。在不超过背包容量的情况下能够装入最大的价值为多少?(这个背包可以不装满)。

与前边的01背包类似,不同之处在于第i件物品的数目为n[i],这里的分析思路就是针对第i种物品,分别可以装入0,1,2,3, … ,n[i]件(同时还得满足不能超过背包的容量)。

dp[i][j] 为将前i件物品装进容量为j的背包可以获得的最大价值, 0<=i<=N, 0<=j<=C

dp表为(N+1)x(C+1)维的二维数组
  • 状态转移方程
1. 不装入第i种物品时,dp[i][j] = dp[i-1][j];

2. 对于第i种物品, k为装入第i种物品的件数, k <= min(n[i], j/w[i])
dp[i][j] = max{(dp[i-1][j − k*w[i]] + k*v[i]) for i in range(k)}

	dp[i][j] = max(dp[i][j], dp[i][j-k* w[i]]+ k* v[i])  
  • base case
第0个物品时不存在的,价值为0。
dp[0][:] = 0;
  • 基本的实现过程:
// 定义dp
vector<vector<int>> dp(N+1, vector<int>(C+1, 0))

// 定义base case
for (int j = 0; j < c+1; j++)
	dp[0][j] = 0;
	
// 执行状态转移
for (int i = 1; i < N+1; i++){
	for (int j = C; j >=0 ; j--){
		dp[i][j] = dp[i-1][j];
		int tmp = min(n[i], j / w[i]);
		for (int k = 0; k<=tmp; k++){
			dp[i][j]  = max(dp[i][j], dp[i][j-k*w[i]] + k*v[i]);	
		}
	}
}
return dp[N][C];
  • 优化的实现过程(dp采用一维数组)
初始dp[j]均为0
for (int i = 1; i < N+1; i++){
	for (int j = C; j >= 0; j--){
	
		int tmp = min(n[i], j / w[i]);
		
		for (int k = 0; k<=tmp; k++){
			dp[j]  = max(dp[j], dp[j-k*w[i]] + k*v[i]);	
		}
	}
}
  • 416 分割等和子集(medium)
  • 494 目标和(medium)
  • 474 一和零(medium)
  • 322 零钱兑换(medium)
  • 518 零钱兑换 II(medium)
  • 139 单词拆分(medium)
  • 377 组合总和 Ⅳ(medium)

416 分割等和子集(medium)

  • 01背包问题
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        if ( n < 2) return false;
        int numsSum = 0;
        for (auto num: nums) numsSum += num;
        if (numsSum %2 != 0) return false;
        int target = numsSum / 2;
        // 这就是一个01背包问题, 背包的容量为target, 能否恰好装满这个背包
        // nums数组的每个元素就是一种物品,nums[i]即为第i种物品的重量。
        vector<vector<bool>> dp(n+1, vector<bool>(target+1, false));
        dp[0][0] = true;
        for(int i = 1; i <= n; i++){
            for (int j = target; j>=0; j--){
                dp[i][j] = dp[i-1][j];
                if (j >= nums[i-1])
                    dp[i][j] = dp[i][j] || dp[i-1][j-nums[i-1]];
                if (dp[i][target] == true)
                    return true;
            }
        }
        return false;
    }
};
  • 优化后的一维数组解决方案
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        if ( n < 2) return false;
        int numsSum = 0;
        for (auto num: nums) numsSum += num;
        if (numsSum %2 != 0) return false;
        int target = numsSum / 2;
        // 这就是一个01背包问题, 背包的容量为target, 能否恰好装满这个背包
        // nums数组的每个元素就是一种物品,nums[i]即为第i种物品的重量。
        vector<bool>dp (target+1, false);
        dp[0] = true;
        for(int i = 1; i <= n; i++){
            for (int j = target; j>=0; j--){
                if (j >= nums[i-1])
                    dp[j] = dp[j] || dp[j-nums[i-1]];
                if (dp[target] == true)
                    return true;
            }
        }
        return false;
    }
};

494 目标和(medium)

  • 01 背包问题, 求方案数目
  • sum§ - sum(N) = target
  • sum§ + sum(N) + sum§ - sum(N) = target + sum§ + sum(N)
  • 2 * sum§ = target + sum(nums)
  • target为计算后的target,找子序列和为target的个数
  • 背包容量为target,物品重量为元素的值
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int sum = 0;
        for(int &num: nums) sum += num;
        if(S > sum || sum < -S) return 0; 
        if((S + sum) % 2 != 0) return 0; 
        int target = (S + sum) / 2;

        vector<int>dp(target + 1, 0);

        dp[0] = 1;
        for(int i = 1; i <= nums.size(); i++)
            for(int j = target; j >= nums[i-1]; j--)
                dp[j] = dp[j] + dp[j - nums[i-1]];

        return dp[target];
    }
};

474 一和零(medium)

  • 01背包问题, 二维背包问题
  • 背包的容量为m与n
  • 每个物品的重量为0的个数与1的个数
  • 每个物品的价值均为1, 求价值最大问题。
  • dp[j][k] = max(dp[j][k], dp[j-nums[i][0]][k - nums[i][1])
class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> nums(strs.size(), vector<int>(2, 0));
        int num0 = 0, num1 = 0;
        for(int i = 0; i<strs.size(); i++){
            nums[i][0] = count(strs[i].begin(), strs[i].end(), '0');
            nums[i][1] = count(strs[i].begin(), strs[i].end(), '1');
            num0 += nums[i][0];
            num1 += nums[i][1];
        }
        for (auto s: nums)
            cout<<s[0] << "  "<< s[1]<<endl;

        if (num0 == m && num1 == n) return nums.size();

        vector<vector<int>> dp (m+1, vector<int>(n+1, 0));
        for (int i = 0; i < nums.size(); i++){
            for (int j = m; j >= nums[i][0]; j--){
                for (int k = n; k >= nums[i][1]; k--){
                    dp[j][k] = max(dp[j][k], dp[j - nums[i][0]][k - nums[i][1]] + 1);
                }
            }
        }
        return dp[m][n];
    }
};

322 零钱兑换(medium)

  • 完全背包问题
  • 背包容量为amount
  • 每件物品的重量为coins[i], 每件物品的价值为1, 求刚好装满背包的物品的价值最小。
  • dp[j] = min(dp[j], dp[j-coins[i-1]]+1)
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        
        vector<int> dp(amount+1, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i < coins.size() + 1; i++){
            for (int j = coins[i-1]; j <= amount; j++){
                if(dp[j] - 1 > dp[j - coins[i-1]])
                    dp[j] = min(dp[j], 1 + dp[j - coins[i-1]]);   
            }
        }
        return dp[amount]==INT_MAX ? -1 : dp[amount];
    }
};

518 零钱兑换 II(medium)

  • 完全背包问题
  • 背包的容量为amount, 每个物品的重量为coins[i],求刚好装满背包的方案数
  • dp[j] = sum(dp[j] + dp[j-coins[i-1]])
class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        vector<int> dp(amount+1, 0);
        dp[0] = 1;
        for (int i = 1; i< n+1; i++){
            for (int j = coins[i-1]; j<= amount; j++)
                dp[j] = dp[j] + dp[j- coins[i-1]];
        }
        return dp[amount];
    }
};
  • 接下来的这两道题,需要考虑输出的顺序,因此循环遍历的顺序与前边几道题不一致,外层遍历背包,内层遍历物品

139 单词拆分(medium)

  • 完全背包
  • 物品就是单词字典,每个物品可以有无数个, 背包就是字符串, 看能否完全装满背包
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;
        for (int i = 1; i <= s.size(); i++){ // 遍历背包
            for (int j = 0; j < i; j++){  // 遍历物品
                string word = s.substr(j, i - j); // 
                if (wordSet.find(word) != wordSet.end())
                    dp[i] = dp[i] || dp[j];
            }
        }
        return dp[s.size()];
    }
};

377 组合总和 Ⅳ(medium)

  • 完全背包问题
  • 物品的重量为nums[i],背包容量为target, 刚好装满背包的组合数
  • dp[j] = sum(dp[j], dp[j-nums[i-1]])
class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        int n = nums.size();
        vector<int> dp(target+1, 0);
        dp[0] = 1;
        for (int i = 0; i < target+1; i++){ // 遍历背包
            for (int j = 1; j < n+1; j++ ){ // 遍历物品
                if ( i >= nums[j-1])
                    dp[i] = (dp[i] >= INT_MAX - dp[i-nums[j-1]]) ? INT_MAX : dp[i] + dp[i-nums[j-1]];
            }
        }
        return dp[target];
    }
};

更多分类刷题资料

  • 微信公众号: 小哲AI

    wechat_QRcode

  • GitHub地址: https://github.com/lxztju/leetcode-algorithm

  • csdn博客: https://blog.csdn.net/lxztju

  • 知乎专栏: https://www.zhihu.com/column/c_1101089619118026752

  • AI研习社专栏:https://www.yanxishe.com/column/109


本文链接: http://www.dtmao.cc/news_show_700128.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?