热门标签 | 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;欢迎常来我博客看看。
在这里插入图片描述



推荐阅读
  • 汇编语言:编程世界的始祖,连C语言都敬畏三分!
    当C语言还在萌芽阶段时,它首次接触到了汇编语言,并对其简洁性感到震惊。尽管汇编语言的指令极其简单,但它却是所有现代编程语言的基础,其重要性不言而喻。 ... [详细]
  • 实现系统调用
    实现系统调用一、实验环境​本次操作还是基于上次编译Linux0.11内核的实验环境进行操作。环境如下:二、实验目标​通过对上述实验原理的认识,相信 ... [详细]
  • 本文详细介绍了在单片机编程中常用的几个C库函数,包括printf、memset、memcpy、strcpy和atoi,并提供了具体的使用示例和注意事项。 ... [详细]
  • JUnit下的测试和suite
    nsitionalENhttp:www.w3.orgTRxhtml1DTDxhtml1-transitional.dtd ... [详细]
  • 深入探讨前端代码优化策略
    本文深入讨论了前端开发中代码优化的关键技术,包括JavaScript、HTML和CSS的优化方法,旨在提升网页加载速度和用户体验。 ... [详细]
  • Go从入门到精通系列视频之go编程语言密码学哈希算法(二) ... [详细]
  • 本文详细介绍了C++中的构造函数,包括其定义、特点以及如何通过构造函数进行对象的初始化。此外,还探讨了转换构造函数的概念及其在不同情境下的应用,以及如何避免不必要的隐式类型转换。 ... [详细]
  • c语言二元插值,二维线性插值c语言
    c语言二元插值,二维线性插值c语言 ... [详细]
  • PHP面试题精选及答案解析
    本文精选了新浪PHP笔试题及最新的PHP面试题,并提供了详细的答案解析,帮助求职者更好地准备PHP相关的面试。 ... [详细]
  • 本文将深入探讨 Unreal Engine 4 (UE4) 中的距离场技术,包括其原理、实现细节以及在渲染中的应用。距离场技术在现代游戏引擎中用于提高光照和阴影的效果,尤其是在处理复杂几何形状时。文章将结合具体代码示例,帮助读者更好地理解和应用这一技术。 ... [详细]
  • 深入浅出C语言指针
    指针是C语言中极其重要的数据类型,广泛应用于各种数据结构的表示、数组和字符串的操作以及内存地址的处理。本文将通过实例详细解析指针的基本概念及其应用。 ... [详细]
  • 本文将详细介绍如何使用Java编程语言生成指定数量的不重复随机数,包括具体的实现方法和代码示例。适合初学者和有一定基础的开发者参考。 ... [详细]
  • OBS Studio自动化实践:利用脚本批量生成录制场景
    本文探讨了如何利用OBS Studio进行高效录屏,并通过脚本实现场景的自动生成。适合对自动化办公感兴趣的读者。 ... [详细]
  • 3.[15]Writeaprogramtolistallofthekeysandvaluesin%ENV.PrinttheresultsintwocolumnsinASCIIbet ... [详细]
  • 编译原理中的语法分析方法探讨
    本文探讨了在编译原理课程中遇到的复杂文法问题,特别是当使用SLR(1)文法时遇到的多重规约与移进冲突。文章讨论了可能的解决策略,包括递归下降解析、运算符优先级解析等,并提供了相关示例。 ... [详细]
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社区 版权所有