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

深入解析C语言中的动态规划算法:以背包问题为例

本文深入探讨了C语言中动态规划算法的应用,以经典的背包问题为例进行详细解析。通过实例分析,展示了如何利用动态规划解决复杂优化问题,并提供了高效的代码实现方法。文章不仅涵盖了算法的基本原理,还讨论了其在实际编程中的应用技巧和优化策略,为读者提供了全面的理解和实践指导。

       作为一名大三老学长,我的嵌入式春招找实习之旅好像接近尾声了。春招投递了BAT、美团、华为、oppo、大疆等公司的实习。大多数公司都给了面试机会,尤其是阿里,笔试一道编程题都没有写出来居然还给了面试机会!还是非常感谢这些互联网公司能够给我面试机会的,oppo 的HR面后半个多月了也没有消息,华为投递一个月也没有什么进展。目前已经拿到了大疆、CVTE实习,打算5月去深圳大疆实习!
        尽管已经拿到了实习的机会,但是通过春招发现了很多的知识空白需要填补,毕竟生于忧患,死于安乐嘛。笔试了很多家公司,编程题总结起来就是字符串、动态规划、二叉树、图、BFS、DFS。一个搞嵌入式的为什么要整这么难的笔试题?八成是因为内卷吧!所以为了秋招,把该补的知识还是得赶快补上,该刷的题还是得刷起来!

往期推荐:

       看完这些面试必问的Linux小知识,我保证你面试后会来给我的文章一键三连
       经过笔试和多轮技术面试我居然败给了HR面?
在这里插入图片描述



文章目录

    • 01背包问题
    • 完全背包问题
    • 多重背包问题
    • 动态规划解题思路


01背包问题

       给定n种物品,和一个容量为C的背包,物品i的重量是w[i],其价值为v[i]。问如何选择装入背包的物品,使得装入背包中的总价值最大?(面对每个武平,只能有选择拿取或者不拿两种选择,不能选择装入某物品的一部分,也不能装入物品多次)


  • 声明一个数组f[n][c]的二维数组,f[i][j]表示在面对第i件物品,且背包容量为j时所能获得的最大价值。
  • 根据题目要求进行打表查找相关的边界和规律
  • 根据打表列写相关的状态转移方程
  • 用程序实现状态转移方程

真题演练:

       一个旅行者有一个最多能装M公斤的背包,现在有n件物品,它们的重量分别是W1、W2、W3、W4、…、Wn。它们的价值分别是C1、C3、C2、…、Cn,求旅行者能获得最大价值。

输入描述:

       第一行&#xff1a;两个整数&#xff0c;M&#xff08;背包容量&#xff0c;M<&#61; 200)和N&#xff08;物品数量&#xff0c;N<&#61;30);
       第2…N&#43;1行&#xff1a;每行两个整数Wi&#xff0c;Ci&#xff0c;表示每个物品的质量与价值。

输出描述&#xff1a;

       仅一行&#xff0c;一个数&#xff0c;表示最大总价值

样例&#xff1a;

输入&#xff1a;10 42 13 34 57 9
输出&#xff1a;12

解题步骤


  1. 定义一个数组dp[i][j]表示容量为j时&#xff0c;拿第i个物品时所能获取的最大价值
  2. 按照题目要求进行打表&#xff0c;列出对应的dp表。

W[i]&#xff08;质量&#xff09;V[i]&#xff08;价值&#xff09;012345678910
00000000000
2100111111111
3300133444444
4500135568899
790013556991012

       对于一个动态规划问题设置下标时最好从0开始&#xff0c;因为动态规划经常会和上一个状态有关系&#xff01;从上面的dp表可以看出来对于一个物品我们拿还是不难需要进行两步来判断。第一步&#xff1a;判断背包当前的容量j是否大于物品当前的质量&#xff0c;如果物品的质量大于背包的容量那么就舍弃。第二步&#xff1a;如果背包可以装下这个物品&#xff0c;就需要判断装下该物品获取的最大价值是不是大于不装下这个物品所获取的最大价值&#xff0c;如果大于那么就把东西装下&#xff01;根据这样的思想我们可以得到状态转移方程&#xff1a;

如果单签背包的容量可以装下物品:dp[i][j]&#61;max(dp[i-1][j],dp[i-1][j-w[i]]&#43;v[i]);
如果当前背包的容量装不下该物品:dp[i][j]&#61;dp[i-1][j];

#include
int max(const int a,const int b)
{return a>b ? a:b;
}
int main()
{int w[35]&#61;{0},v[35]&#61;{0},dp[35][210]&#61;{0};int n,m;scanf("%d %d",&m,&n);int i,j;for(i&#61;1;i<&#61;n;i&#43;&#43;){scanf("%d %d",&w[i],&v[i]);}for(i&#61;1;i<&#61;n;i&#43;&#43;){for(j&#61;1;j<&#61;m;j&#43;&#43;){if(j>&#61;w[i])//如果当前背包的容量大于商品的质量{dp[i][j]&#61;max(dp[i-1][j],dp[i-1][j-w[i]]&#43;v[i]);//判断是否应该拿下}else//大于背包的当前容量{dp[i][j]&#61;dp[i-1][j];}}}for(int k&#61;0;k<&#61;n;k&#43;&#43;){for(int l&#61;0;l<&#61;m;l&#43;&#43;){printf("%d ",dp[k][l]);}printf("\n");}printf("%d\n",dp[n][m]);
}

在这里插入图片描述

       通过运行以上程序可以看到最终的输出dp表和我们的预期是相符合的&#xff01;但是并没有结束&#xff0c;动态规划有一个后无效性原则(当前状态只与前一个状态有关)。那么我们就可以对dp数组进行压缩处理&#xff0c;将二维数组转换成一维数组。每一次选择物品对这个数组进行更新就可以啦&#xff01;那么就可以将状态转移方程压缩成为 dp[j]&#61;max(dp[j],dp[j-w[i]]&#43;v[i]) 。不过我们需要注意的是在压缩过后我们需要逆序刷新数组的值&#xff0c;如果正序刷新的话就不能保存上一个阶段对应获取最大价值的值了。那么我们就可以写出以下程序&#xff1a;

#include
int max(const int a,const int b)
{return a>b ? a:b;
}
int main()
{int w[35]&#61;{0},v[35]&#61;{0},dp[210]&#61;{0};int n,m;scanf("%d %d",&m,&n);int i,j;for(i&#61;1;i<&#61;n;i&#43;&#43;){scanf("%d %d",&w[i],&v[i]);}for(i&#61;1;i<&#61;n;i&#43;&#43;){for(j&#61;m;j>&#61;0;j--){if(j>&#61;w[i])//如果当前背包的容量大于商品的质量{dp[j]&#61;max(dp[j],dp[j-w[i]]&#43;v[i]);//判断是否应该拿下}}for(int k&#61;0;k<&#61;m;k&#43;&#43;){printf("%d ",dp[k]);}printf("\n");}printf("%d\n",dp[n][m]);
}

在这里插入图片描述
       可以看出和上面输出的dp表并没有什么区别&#xff01;


完全背包问题

题目描述&#xff1a;

       设有n种物品&#xff0c;每种物品有一个重量及一个价值&#xff0c;但每种物品的数量都是无限的&#xff0c;有一个背包&#xff0c;最大载重量为m&#xff0c;今从n中物品中选取若干件&#xff08;同一种物品可以多次选取&#xff09;使其质量小于等于m&#xff0c;而价值的和为最大。

输入&#xff1a;

        第一行&#xff1a;两个整数&#xff0c;M&#xff08;背包容量&#xff0c;M<&#61; 200)和N&#xff08;物品数量&#xff0c;N<&#61;30);
        第2…N&#43;1行&#xff1a;每行两个整数Wi&#xff0c;Ci&#xff0c;表示每个物品的质量与价值。

输出&#xff1a;

       仅一行&#xff0c;一个数&#xff0c;表示最大总价值。

样例&#xff1a;

输入:
10 4
2 1
3 3
4 5
7 9
输出:
12

       与01背包问题不同的是这不是每个物品选择拿与不拿的问题了&#xff0c;而是要选择几个该物品&#xff0c;最终选择价值最大的。那么我们可以在01背包的问题上继续进行思考这个问题&#xff0c;01背包中我们知道了之前的状态&#xff0c;那么我无非就是要判断拿k个物品和不拿时进行比较&#xff0c;如果价值比之前大就拿下。而每个种类的物品最多只能拿取j/w[i]个&#xff0c;再加一重循环不就可以啦&#xff01;程序的核心代码如下&#xff1a;

for(i&#61;1;i<&#61;n;i&#43;&#43;){for(j&#61;m;j>&#61;0;j--){for(k&#61;0;k<&#61;j/w[i];k&#43;&#43;){dp[j]&#61;max(dp[j],dp[j-k*w[i]]&#43;k*v[i]);//判断是否应该拿下k个商品}}
}

       通过代码可以发现通过这种朴素的算法是需要三重循环的&#xff0c;好像对时间复杂度比较高。那么我们也借鉴01背包来对完全背包进行打表&#xff01;


w[i]&#xff08;质量&#xff09;v[i]&#xff08;价值&#xff09;012345678910
00000000000
2100112233445
3300133466799
4500135568101011
7900135569101012

       根据表中红色标记的数值来看&#xff0c;需要注意的是如果背包的容量不能装下当前物品的质量。那么当前容量所能装下价值最大的物品就等于上一个物品所能保存的最大价值。重点看一下4是怎么来的&#xff0c;这个4并不是从 i-1来的&#xff0c;而是从i来的。通过正序推出该物品的价值。状态转移方程就可以写成是 &#xff1a;dp[i][j]&#61;max(dp[i-1][j],dp[i][j-w[i]]&#43;v[i]) 和01背包的唯一区别是max的第二个参数。01背包是i-1&#xff0c;而完全背包是i&#xff0c;而且是通过正序推理得到的状态转移方程。

       根据状态转移方程应该很快就能写出程序了吧&#xff01;但是根据dp的后无效性原则&#xff0c;对动态规划状态转移方程进行压缩&#xff01;压缩过后就是dp[j]&#61;max(dp[j],dp[j-w[i]]&#43;v[i]) &#xff0c;小伙伴们一看是不是和01背包的状态转移方程一模一样啊&#xff01;但是但是两个有个重大的区别&#xff1a;01背包使用的是上一条的数据&#xff0c;所以需要逆序避免覆盖之前的值&#xff0c;而完全背包是从当前更新后的数据进行相关的操作的 。通过以上分析我们可以写出如下程序&#xff1a;

#include
int max(const int a,const int b)
{return a>b ? a:b;
}
int main()
{int w[35]&#61;{0},v[35]&#61;{0},dp[210]&#61;{0};int n,m;scanf("%d %d",&m,&n);int i,j;for(i&#61;1;i<&#61;n;i&#43;&#43;){scanf("%d %d",&w[i],&v[i]);}for(i&#61;1;i<&#61;n;i&#43;&#43;){for(j&#61;0;j<&#61;m;j&#43;&#43;){if(j>&#61;w[i])//如果当前背包的容量大于商品的质量{dp[j]&#61;max(dp[j],dp[j-w[i]]&#43;v[i]);//判断是否应该拿下}}for(int k&#61;0;k<&#61;m;k&#43;&#43;){printf("%d ",dp[k]);}printf("\n");}printf("%d\n",dp[m]);
}

在这里插入图片描述

       通过以上代码的输出可以看出打印的dp表和我们推测的并没有什么区别&#xff0c;程序正确&#xff01;


多重背包问题

题目描述&#xff1a;

       为了庆祝班级在校运会上取得了全校第一名的好成绩&#xff0c;班主任决定开一场庆功会&#xff0c;为此拨款购买奖品犒劳运动员。期望拨款金额能够购买最大价值的奖品&#xff0c;可以补充他们的精力和体力。

输入&#xff1a;

       第一行输入两个数n&#xff08;n<&#61;500),m(m<&#61;6000)&#xff0c;其中n代表希望购买的奖品的种数&#xff0c;m表示拨款金额。

       接下来的n行&#xff0c;每行3个数,w,v,s分别表示第i种奖品的价格、价值&#xff08;价格与价值是不同的概念&#xff09;和能购买的最大数量&#xff08;买0件到s件均可&#xff09;&#xff0c;其中w<&#61;100,v<&#61;1000,s<&#61;10;

输出&#xff1a;

       一行&#xff1a;一个数&#xff0c;表示此次购买能获得的最大价值&#xff08;注意&#xff01;不是价格&#xff09;。

示例&#xff1a;

输入&#xff1a;
5 1000
输出&#xff1a;
80 20 4
40 50 9
30 50 7
40 30 6
20 20 1

       与完全背包不同的是&#xff1a;完全背包每个物品的个数是无限的&#xff0c;而多重背包是每个物品只能拿指定的件数。那么最容易想到的方法就是把相同的物品分开&#xff0c;比如说有n个a物品&#xff0c;就将它分成a1 a2 a3 a4…an然后用01背包的方法去解决。那么我们就可以写出以下核心代码&#xff1a;

for(i&#61;1;i<&#61;n;i&#43;&#43;){for(j&#61;m;j>&#61;0;j--){for(k&#61;0;k<&#61;s[i]&&j>&#61;k*w[i];k&#43;&#43;){dp[j]&#61;max(dp[j],dp[j-k*w[i]]&#43;k*v[i]);//从01背包的状态转移方程&#xff0c;去增加第i个物品拿k个的循环}}
}

       通过以上的代码可以看出当s[i]特别大的时候那么就会消耗非常多的时间复杂度&#xff0c;那么肯定是有优化的方法的&#xff01;那么我们可以通过二进制来对这个同一个物品应该拿取几个进行优化。我们可以通过以下问题进行研究&#xff1a;

有1000个苹果&#xff0c;10个箱子怎么放&#xff0c;不管我想拿多少个苹果&#xff0c;都可以成箱成箱的拿&#xff1f;

       用二进制的思想就是每一个箱子代表二进制对应的位数&#xff0c;那么210大于1024应该是可以满足题目条件的。那么每个箱子放的苹果分别是1,2,4,8,16,32&#xff0c;…488&#xff08;1000-512&#xff09;。需要一个苹果拿第一箱&#xff0c;需要两个苹果拿第二项&#xff0c;需要三个苹果拿一二箱。那么对于需要拿1000箱的问题本来要循环1000次&#xff0c;经过优化以后只用循环10次就可以啦&#xff01;那么我们就可以写出以下程序啦&#xff01;

for(i&#61;1;i<&#61;n;i&#43;&#43;){for(j&#61;m;j>&#61;0;j--){for(k&#61;0;k<&#61;s[i]&&j>&#61;k*w[i];k<<&#61;1){if((k<<1)>s[i]&&j>&#61;k*w[i]){dp[j]&#61;max(dp[j],dp[j-(s[i]-k)*w[i]]&#43;(s[i]-k)*v[i]);}elsedp[j]&#61;max(dp[j],dp[j-k*w[i]]&#43;k*v[i]);//从01背包的状态转移方程&#xff0c;去增加第i个物品拿k个的循环}}
}

动态规划解题思路

       对于动态规划问题我们一般的思路如下&#xff1a;


  • 判断是动态规划的解题思路以后立马定义一个数组&#xff0c;把数组对应的下标、对应的值想清楚。
  • 然后根据题目意思找规律进行打表&#xff0c;找出初始状态以及一些边界条件。
  • 根据打表的数据找出状态转移方程。
  • 最后根据状态转移方程进行编写程序。

       不积小流无以成江河&#xff0c;不积跬步无以至千里。而我想要成为万里羊&#xff0c;就必须坚持学习来获取更多知识&#xff0c;用知识来改变命运&#xff0c;用博客见证成长&#xff0c;用行动证明我在努力。
       如果我的博客对你有帮助、如果你喜欢我的博客内容&#xff0c;记得“点赞” “评论” “收藏”一键三连哦&#xff01;听说点赞的人运气不会太差&#xff0c;每一天都会元气满满呦&#xff01;如果实在要白嫖的话&#xff0c;那祝你开心每一天&#xff0c;欢迎常来我博客看看。
在这里插入图片描述



推荐阅读
  • AIX编程挑战赛:AIX正方形问题的算法解析与Java代码实现
    在昨晚的阅读中,我注意到了CSDN博主西部阿呆-小草屋发表的一篇文章《AIX程序设计大赛——AIX正方形问题》。该文详细阐述了AIX正方形问题的背景,并提供了一种基于Java语言的解决方案。本文将深入解析这一算法的核心思想,并展示具体的Java代码实现,旨在为参赛者和编程爱好者提供有价值的参考。 ... [详细]
  • 2012年9月12日优酷土豆校园招聘笔试题目解析与备考指南
    2012年9月12日,优酷土豆校园招聘笔试题目解析与备考指南。在选择题部分,有一道题目涉及中国人的血型分布情况,具体为A型30%、B型20%、O型40%、AB型10%。若需确保在随机选取的样本中,至少有一人为B型血的概率不低于90%,则需要选取的最少人数是多少?该问题不仅考察了概率统计的基本知识,还要求考生具备一定的逻辑推理能力。 ... [详细]
  • 在编程笔试和面试中,全排列算法因其适中的难度而备受青睐,不仅能够考察应聘者的算法基础,还能测试其对递归和回溯的理解。本文将深入解析全排列算法的实现原理,探讨其应用场景,并提供优化建议,帮助读者更好地掌握这一重要算法。 ... [详细]
  • 总数 | 小规模算法动态规划第3讲:LeetCode 62 不同路径详解 | 从自顶向下到自底向上的动态规划方法分析
    总数 | 小规模算法动态规划第3讲:LeetCode 62 不同路径详解 | 从自顶向下到自底向上的动态规划方法分析 ... [详细]
  • 掌握Android UI设计:利用ZoomControls实现图片缩放功能
    本文介绍了如何在Android应用中通过使用ZoomControls组件来实现图片的缩放功能。ZoomControls提供了一种简单且直观的方式,让用户可以通过点击放大和缩小按钮来调整图片的显示大小。文章详细讲解了ZoomControls的基本用法、布局设置以及与ImageView的结合使用方法,适合初学者快速掌握Android UI设计中的这一重要功能。 ... [详细]
  • 揭秘腾讯云CynosDB计算层设计优化背后的不为人知的故事与技术细节
    揭秘腾讯云CynosDB计算层设计优化背后的不为人知的故事与技术细节 ... [详细]
  • 掌握PHP编程必备知识与技巧——全面教程在当今的PHP开发中,了解并运用最新的技术和最佳实践至关重要。本教程将详细介绍PHP编程的核心知识与实用技巧。首先,确保你正在使用PHP 5.3或更高版本,最好是最新版本,以充分利用其性能优化和新特性。此外,我们还将探讨代码结构、安全性和性能优化等方面的内容,帮助你成为一名更高效的PHP开发者。 ... [详细]
  • 深入理解 Java 控制结构的全面指南 ... [详细]
  • 深入解析 Golang 中 Context 的功能与应用
    本文详细探讨了 Golang 中 Context 的核心功能及其应用场景,通过深入解析其工作机制,帮助读者更好地理解和运用这一重要特性,对于提升代码质量和项目开发效率具有重要的参考价值。 ... [详细]
  • 本文深入探讨了URAL 1297问题,重点分析了使用后缀数组求解最长回文子串的方法。通过详细解析算法的实现步骤和优化策略,本文提供了高效的解决方案,并结合实际案例进行了验证。此外,文章还讨论了后缀数组在字符串处理中的广泛应用及其性能优势。 ... [详细]
  • Netty框架中运用Protobuf实现高效通信协议
    在Netty框架中,通过引入Protobuf来实现高效的通信协议。为了使用Protobuf,需要先准备好环境,包括下载并安装Protobuf的代码生成器`protoc`以及相应的源码包。具体资源可从官方下载页面获取,确保版本兼容性以充分发挥其性能优势。此外,配置好开发环境后,可以通过定义`.proto`文件来自动生成Java类,从而简化数据序列化和反序列化的操作,提高通信效率。 ... [详细]
  • 在解决区间相关问题时,我发现自己经常缺乏有效的思维方式,即使是简单的题目也常常需要很长时间才能找到解题思路,而一旦得到提示便能迅速理解。题目要求对一个包含n个元素的数组进行操作,并给出一个参数k,具体任务是…… ... [详细]
  • 深入理解Linux网络编程:UDP协议实战解析
    深入理解Linux网络编程:UDP协议实战解析 ... [详细]
  • 在处理大图片时,PHP 常常会遇到内存溢出的问题。为了避免这种情况,建议避免使用 `setImageBitmap`、`setImageResource` 或 `BitmapFactory.decodeResource` 等方法直接加载大图。这些函数在处理大图片时会消耗大量内存,导致应用崩溃。推荐采用分块处理、图像压缩和缓存机制等策略,以优化内存使用并提高处理效率。此外,可以考虑使用第三方库如 ImageMagick 或 GD 库来处理大图片,这些库提供了更高效的内存管理和图像处理功能。 ... [详细]
  • 从2019年AI顶级会议最佳论文,探索深度学习的理论根基与前沿进展 ... [详细]
author-avatar
baiwei001
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有