算法基础课：动态规划之背包问题-白红宇的个人博客

发布日期：2022-02-28 07:22:42 浏览次数：26 分类：技术文章

本文共 483 字，大约阅读时间需要 1 分钟。

首先动态规划，应该理解为一个递推的过程，很多时候对于动态规划来说都应该是从前向后递推的一个过程。但是思考的方式还是应该按照递归的思想来去思考，比如说按照集合划分，状态表示，状态表示又可以划分成状态表示的东西是什么？状态表示的条件是什么，属性又是什么？状态计算就是正常的一个递推的过程，思考方式是该属性可以来源于哪些部分，然后然后以递推的方式进行即可。

01背包：每个物体只有选与不选。

完全背包：每个物体可以选择无数次。

多重背包：每个物体只能选择有限次。

分组背包：分成若干组，每次只能从每组之中选择一个（类似01背包）

其实都是推公式加变形的一个过程，具体的东西需要自己一步步推导。

这里重点讲下多重背包的二进制优化问题。

原始问题的时间复杂度O(NMS)变成O(NMlogs)

核心原理就是：对于任意的数都可以用二进制表示：

举例：对于200可以用1，2，4，。。。。64来表示1-127同时再加上一个C特别注意此C小于128。

然后原始的问题可以转换成：把S转成此种表示方式，存入到V[I]和W[I]数组中去，然后原始的问题就可以转换成0，1背包模型来解决。

转载地址：https://blog.csdn.net/weixin_45854106/article/details/107115677 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：算法基础课：集合结构

下一篇：算法基础课：区间DP

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章