热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

动态规划之01背包和完全背包问题(力扣C++题解)

理论内容都在代码随想录了,这里我主要是自己写题解回顾,强烈推荐代码随想录代码随想录PDF,代码随想录百度网盘,代码随想录知识星球,代码随想录八股文PDF,代码随想录刷题路线,代码随

理论内容都在代码随想录了,这里我主要是自己写题解回顾,强烈推荐

代码随想录代码随想录PDF,代码随想录百度网盘,代码随想录知识星球,代码随想录八股文PDF,代码随想录刷题路线,代码随想录知识星球八股文https://www.programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-1.html

 

目录

模板一:二维数组版本

 模板二:一维数组版本(滚动数组)

1:分割等和子集(01背包)

2:最后一块石头的重量 II(01背包)

3:目标和(组合问题)

 4:一和零

完全背包:

5:零钱兑换||(组合问题)

6:零钱兑换||||(排列总和)




模板一:二维数组版本

void test_2_wei_bag_problem1() {
vector weight = {1, 3, 4};
vector value = {15, 20, 30};
int bagweight = 4;
// 二维数组
vector> dp(weight.size(), vector(bagweight + 1, 0));
// 初始化
for (int j = weight[0]; j <= bagweight; j++) {
dp[0][j] = value[0];
}
// weight数组的大小 就是物品个数
for(int i = 1; i for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
if (j else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
cout <}
int main() {
test_2_wei_bag_problem1();
}

问题:


(1)初始化问题:不能随意的凭感觉的初始化为0,或初始化为1,要根据实际情况

当这个点是初始点时,将数据带入,并检查,因为这个点时所有点的基石

当这个点不为初始点时,一般初始化为0(防止覆盖后面递推得出的数据)

比如在这个模板中:将第一行全部初始化为value[0]

意义为:当背包容量>=1时,如果只放第一件物品,那么背包所得到的最大价值就是value[0]



 (2)for循环遍历顺序问题:

一般我们都是先正序遍历物品的重量,再正序遍历背包容量,但实际上,在二维数组中,这个顺序完全可以颠倒,即先正序遍历背包容量,再正序遍历物品的重量;

因为它们之间互相不会覆盖,所以不受影响,但是下面的一维数组就要考虑了



(3)递推公式问题:01背包模板递推公式:

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])

含义:dp[i][j] 表示从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少

返回即返回dp[weight.size()-1][bagweight],也就是递推的最后一步

当不放入物品时:背包容量没有损失,最大价值等于上一个的价值(没有拿,价值不变)

当放入物品时:背包容量=背包容量-物品的重量,最大价值等于上一个的价值+新增物品的价值



 模板二:一维数组版本(滚动数组)

#include
#include
#include
#include
using namespace std;
void test()
{
vector weight = { 1, 3, 4 };
vector value = { 15, 20, 30 };
int bagweight = 4;
//核心是:物品重量作为底,将背包的最大容量作为天花板,将天花板依次--,直到正好等于底
//依次统计天花板降低时,dp[j]的最大价值
//之后再重新换一个底,重复上述步骤
vector dp(bagweight + 1, 0);
for (int i = 0; i {
for (int j = bagweight; j >= weight[i]; j--)//背包容量
{
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
cout <}
int main()
{
test();
return 0;
}
dp[4]=max(dp[4]),dp[4-1]+15)=max(dp[4],dp[3]+15) j=4
dp[3]=max(dp[3],dp[4-1]+15)=max(dp[3],dp[2]+15) j=3
dp[2]=max(dp[2],dp[1]+15) j=2 ->>
dp[1]=max(dp[1],dp[0]+15) j=1 ->> dp[1]=max(0,15)=15
dp[4]=max(dp[4],dp[4-3]+vaule[1])=max(dp[4],dp[1]+20)=max(0,15+20)=35
dp[3]=max(dp[3],dp[3-3]+value[1])=max(dp[3],dp[0]+20)=max(0,0+20)=20
dp[4]=max(dp[4],dp[0]+value[2]=max(35,30)=35

问题:


(1)遍历顺序问题:

这里与二维数组的遍历顺序不同,先正序遍历了物品的重量,再逆序遍历了背包的容量,原因是:逆序时你会发现在第一遍遍历时:我的dp[4]不会影响到dp[3],直到第一遍遍历快结束时,dp[1]才给了我们一个具体的数值,到第二遍遍历时,我们才是真正意义上的递推

由于比较难理解,我比较sha地把递推的过程都写了出来(在上面)


 接下来理解下被”影响“的含义:假设我的第二层是正序遍历

dp[1]=max(dp[1],dp[0]+15) j=1 ->> dp[1]=max(0,15)=15
dp[2]=max(dp[2],dp[1]+15) j=2 ->> dp[2]=max(0,30)=30
dp[3]=max(dp[3],dp[4-1]+15)=max(dp[3],dp[2]+15) dp[3]=45
dp[4]=max(dp[4]),dp[4-1]+15)=max(dp[4],dp[3]+15) dp[4]=60

你会发现:物品1被重复放进了背包,这与题目规定的:物品只有一件的条件相违背!

同时,两个for循环的先后顺序也不能颠倒


(2)初始化问题:

一开始是将数组全部初始化为0,经过一次遍历后,数组别重新修改为了15(value[0])



 (3)递推公式问题:

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);(很好理解:大过你就覆盖)

此时的dp[j]和上面的dp[i][j]中的dp[j]含义一样:当背包容量为j时,背包存储的最大价值





1:分割等和子集(01背包)

 思路解析:


这道题实质是将数组分为两部分:

(1)对数组进行求和,总和记录为sum

·····1如果sum为奇数,那么就证明sum无法被拆为两部分,return false;

·····2如果sum为偶数,那么用target=sum/2

(2)相当于只要证明容量为target的背包只要当容量满的时候,它的价值为target即可完成

对于数组中的数字大小,即是它的重量又是它的价值

递推公式为:dp[j]=max(dp[j],dp[j-nums[i]]+nums[i])

(3)判断->相当于(2)的话用代码表示即为:dp[target]==target-->return true;  else false;


class Solution {
public:
bool canPartition(vector& nums) {
int sum = 0;
vectordp(10001, 0);
for (int i = 0; i if (sum % 2) return false;
int target = sum / 2;
for (int i = 0; i {
for (int j = target; j >= nums[i]; j--)
{
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
}
}
if (dp[target] == target) return true;
return false;
}
};

问:为什么dp数组开10001这么大?

答:因为


  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100
  • 总和不会大于20000,背包最大只需要其中一半,+1是为了对齐,我们需要target这个下标



2:最后一块石头的重量 II(01背包)

 思路解析:


这道题很容易联想到将数组分为大小最为接近的两堆,以此得到最优值

(1)对数组进行求和,总和记录为sum

将target=sum/2  分为两半,target和sum-target

但是注意:当sum为偶数时,这两堆相等

当sum为奇数时,由于target=sum/2,向下取整,所以target比sum-target小

(2)既然是求剩下石头重量,那么我们只需让这两个相减即可,当然是大的-小的

所以我们就确定了最后一步:return (sum-dp[target])-dp[target];

接下来的目标就是求dp[target]

(3)递推公式

dp[j]=max(dp[j],dp[j-nums[i]]+nums[i])

同样的在数组中,数字的大小,即是它的价值也是它的重量


class Solution {
public:
int lastStoneWeightII(vector& nums) {
int sum = 0;
vector dp(15001, 0);
for (int i = 0; i int target = sum / 2;
for (int i = 0; i {
for (int j = target; j >= nums[i]; j--)
{
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
}
}
return sum - dp[target] - dp[target];
}
};

解释:dp的大小应该不用我过多解释了^ ^




3:目标和(组合问题)

 思路解析:


这道题与前两题不同的是:前两题求的是价值,这道题求是的数量

由于只有加减法:那么我们就假设加法的数量为x,总数为sum,那么减法的数量为sum-x

即有:x-(sum-x)=target,target为目标值

我们可以进行讨论:

如果总数sum

经过上式则可得x的表达式为:x=(target+sum)/2;

由于x必定为整数,所以target和sum的值必须为偶数

这次和之前遇到的背包问题不一样了,之前都是求容量为j的背包,最多能装多少。

本题则是装满有几种方法。其实这就是一个组合问题了

递推公式为:dp[j] += dp[j - nums[i]]

dp[j] 表示:填满j(包括j)这么大容积的包,有dp[j]种方法


int findTargetSumWays(vector& nums, int target) {
int sum = 0;
for (int i = 0; i if (abs(target) > sum) return 0;
if ((sum + target) % 2 == 1) return 0;
int bagsize = (sum + target) / 2;
vector dp(bagsize + 1, 0);
dp[0] = 1;
for (int i = 0; i {
for (int j = bagsize; j >= nums[i]; j--)
{
dp[j] += dp[j - nums[i]];
}
}
return dp[bagsize];
}

解释:关于dp的初始化:dp[0]=1,当容量为0时,填满它只有一种方法:不填

这么解释虽然很牵强,但是从递推公式我们可以看出,如果初始化为0,那么所有的结果均为0




 4:一和零

 思路解析:

题目的意思:让你返回满足这个条件的最长串

这道题有难…………,因为它的重量变为了两种,0的数量和1的数量,价值呢?字符串的个数

可以简单地理解为:重量是要消耗的,价值是我们想要的结果


(1)遍历整个大串,在大串中遍历小串,在小串中用字符去遍历,统计0和1的个数

(2)遍历顺序:最外层是大串(物品的重量),内层是(背包的容量)(有两个内层!)

(3)递推公式:因为这里是求最优(而不是3题的方法数),所以并非组合问题

dp[i][j]=max(dp[i][j],dp[i-zerosize][j-onesize]+1);


class Solution {
public:
int findMaxForm(vector& strs, int m, int n) {
vector> dp(m + 1, vector (n + 1, 0)); // 默认初始化0
for (string str : strs) { // 遍历物品
int OneNum= 0, zerOnum= 0;
for (char c : str) {
if (c == '0') zeroNum++;
else oneNum++;
}
for (int i = m; i >= zeroNum; i--) { // 遍历背包容量且从后向前遍历!
for (int j = n; j >= oneNum; j--) {
dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
}
}
}
return dp[m][n];
}
};



完全背包:

(1)次数不同

与01背包不同的是,同一件物品,在01背包问题中,只能取1次,而在完全背包问题中,可取无数次(只要背包容量够)



(2)次数不同导致了遍历顺序不同

在01背包中,第二层的for循环我们逆序遍历背包的容量

在完全背包中,第二层的for循环,我们可以正序遍历背包的容量



 (3)组合问题和排序问题

组合问题的遍历方式:先物品再背包(都是正序)

排列问题的遍历方式:变背包再物品(都是正序)


 完全背包模板:

// 先遍历物品,在遍历背包
void test_CompletePack() {
vector weight = {1, 3, 4};
vector value = {15, 20, 30};
int bagWeight = 4;
vector dp(bagWeight + 1, 0);
for(int i = 0; i for(int j = weight[i]; j <= bagWeight; j++) { // 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
cout <}
int main() {
test_CompletePack();
}



5:零钱兑换||(组合问题)

 思路解析:


不考虑顺序,求组合总数

由于是组合总数:所以遍历顺序是:先物品再背包

由于是组合总数:所以递推公式是:dp[j]=dp[j-nums[i]]


class Solution {
public:
int change(int amount, vector& coins) {
vector dp(amount + 1, 0);
dp[0] = 1;
for (int i = 0; i for (int j = coins[i]; j <= amount; j++) { // 遍历背包
dp[j] += dp[j - coins[i]];
}
}
return dp[amount];
}
};



6:零钱兑换||||(排列总和)

 思路解析:


这道题就是妥妥的排列总数题

由于是排列总数:所以遍历顺序为:先背包再物品

由于是排列总数:所以递推公式为:dp[i] += dp[i - nums[j]];(一摸一样)


class Solution {
public:
int combinationSum4(vector& nums, int target) {
vector dp(target + 1, 0);
dp[0] = 1;
for (int i = 0; i <= target; i++) { // 遍历背包
for (int j = 0; j if (i - nums[j] >= 0 ) {
dp[i] += dp[i - nums[j]];
}
}
}
return dp[target];
}
};

解释:防止溢出我把dp的类型换为了unsigned int,期间我试过了int,long long都会溢出

索性换为了unsigned int,没想到居然过了^ ^

题目数据保证答案符合 32 位整数范围

等我问大佬清楚了,再来补充^ ^



推荐阅读
  • 具备括号和分数功能的高级四则运算计算器
    本研究基于C语言开发了一款支持括号和分数运算的高级四则运算计算器。该计算器通过模拟手算过程,对每个运算符进行优先级标记,并按优先级从高到低依次执行计算。其中,加减运算的优先级最低,为0。此外,该计算器还支持复杂的分数运算,能够处理包含括号的表达式,提高了计算的准确性和灵活性。 ... [详细]
  • 本文全面解析了JavaScript中的DOM操作,并提供了详细的实践指南。DOM节点(Node)通常代表一个标签、文本或HTML属性,每个节点都具有一个nodeType属性,用于标识其类型。文章深入探讨了DOM节点的创建、查询、修改和删除等操作,结合实际案例,帮助读者更好地理解和掌握DOM编程技术。 ... [详细]
  • 本文深入解析了Java面向对象编程的核心概念及其应用,重点探讨了面向对象的三大特性:封装、继承和多态。封装确保了数据的安全性和代码的可维护性;继承支持代码的重用和扩展;多态则增强了程序的灵活性和可扩展性。通过具体示例,文章详细阐述了这些特性在实际开发中的应用和优势。 ... [详细]
  • 如何利用Java 5 Executor框架高效构建和管理线程池
    Java 5 引入了 Executor 框架,为开发人员提供了一种高效管理和构建线程池的方法。该框架通过将任务提交与任务执行分离,简化了多线程编程的复杂性。利用 Executor 框架,开发人员可以更灵活地控制线程的创建、分配和管理,从而提高服务器端应用的性能和响应能力。此外,该框架还提供了多种线程池实现,如固定线程池、缓存线程池和单线程池,以适应不同的应用场景和需求。 ... [详细]
  • 作为软件工程专业的学生,我深知课堂上教师讲解速度之快,很多时候需要课后自行消化和巩固。因此,撰写这篇Java Web开发入门教程,旨在帮助初学者更好地理解和掌握基础知识。通过详细记录学习过程,希望能为更多像我一样在基础方面还有待提升的学员提供有益的参考。 ... [详细]
  • ButterKnife 是一款用于 Android 开发的注解库,主要用于简化视图和事件绑定。本文详细介绍了 ButterKnife 的基础用法,包括如何通过注解实现字段和方法的绑定,以及在实际项目中的应用示例。此外,文章还提到了截至 2016 年 4 月 29 日,ButterKnife 的最新版本为 8.0.1,为开发者提供了最新的功能和性能优化。 ... [详细]
  • 本文总结了JavaScript的核心知识点和实用技巧,涵盖了变量声明、DOM操作、事件处理等重要方面。例如,通过`event.srcElement`获取触发事件的元素,并使用`alert`显示其HTML结构;利用`innerText`和`innerHTML`属性分别设置和获取文本内容及HTML内容。此外,还介绍了如何在表单中动态生成和操作``元素,以便更好地处理用户输入。这些技巧对于提升前端开发效率和代码质量具有重要意义。 ... [详细]
  • 贪心策略在算法设计中的应用与优化
    贪心算法在算法设计中具有广泛的应用,特别是在解决优化问题时表现出色。本文通过分析经典问题“买卖股票的最佳时机II”,探讨了贪心策略的基本原理及其在实际问题中的应用。通过实例分析,展示了贪心算法如何通过局部最优选择逐步达到全局最优解,并讨论了其在时间和空间复杂度上的优势。此外,还提出了一些优化方法,以提高算法的效率和适用性。 ... [详细]
  • 2012年9月12日优酷土豆校园招聘笔试题目解析与备考指南
    2012年9月12日,优酷土豆校园招聘笔试题目解析与备考指南。在选择题部分,有一道题目涉及中国人的血型分布情况,具体为A型30%、B型20%、O型40%、AB型10%。若需确保在随机选取的样本中,至少有一人为B型血的概率不低于90%,则需要选取的最少人数是多少?该问题不仅考察了概率统计的基本知识,还要求考生具备一定的逻辑推理能力。 ... [详细]
  • 【图像分类实战】利用DenseNet在PyTorch中实现秃头识别
    本文详细介绍了如何使用DenseNet模型在PyTorch框架下实现秃头识别。首先,文章概述了项目所需的库和全局参数设置。接着,对图像进行预处理并读取数据集。随后,构建并配置DenseNet模型,设置训练和验证流程。最后,通过测试阶段验证模型性能,并提供了完整的代码实现。本文不仅涵盖了技术细节,还提供了实用的操作指南,适合初学者和有经验的研究人员参考。 ... [详细]
  • JavaScript XML操作实用工具类:XmlUtilsJS技巧与应用 ... [详细]
  • 在前文探讨了Spring如何为特定的bean选择合适的通知器后,本文将进一步深入分析Spring AOP框架中代理对象的生成机制。具体而言,我们将详细解析如何通过代理技术将通知器(Advisor)中包含的通知(Advice)应用到目标bean上,以实现切面编程的核心功能。 ... [详细]
  • 深入理解 Java 控制结构的全面指南 ... [详细]
  • 在编程笔试和面试中,全排列算法因其适中的难度而备受青睐,不仅能够考察应聘者的算法基础,还能测试其对递归和回溯的理解。本文将深入解析全排列算法的实现原理,探讨其应用场景,并提供优化建议,帮助读者更好地掌握这一重要算法。 ... [详细]
  • 七款高效编辑器与笔记工具推荐:KindEditor自动换行功能解析
    本文推荐了七款高效的编辑器与笔记工具,并详细解析了KindEditor的自动换行功能。其中,轻笔记QingBiJi是一款完全免费的记事本软件,用户可以通过其简洁的界面和强大的功能轻松记录和管理日常事务。此外,该软件还支持多平台同步,确保用户在不同设备间无缝切换。 ... [详细]
author-avatar
手机用户2602915825_387
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有