在 上一讲 中我们说到，多重背包问题无法像完全背包那样，通过一维空间优化来降低时间复杂度。
其实就是在 0-1 背包问题的基础上，增加了每件物品可以选择「有限次数」的特点（在容量允许的情况下）。
看完前面四篇关于背包问题的文章，你会发现背包问题其实也不过如此，而且它们之间有很多相似的地方，本篇文章就来揭开它们面纱，将背包问题彻底搞定。
在最开始讲解 多重背包 时，我们就提到了「多重背包」的一维空间优化，无法优化时间复杂度。
但其实「多重背包」并没有这么常见，以至于在 LeetCode 上我都没找到与「多重背包」相关的题目。
背包系列，是动态规划里一类典型的问题，主要有：01背包，完全背包，多重背包，混合背包，二维费用背包，分组背包，有依赖背包和泛化物品等。也就是常说的背包九讲。
而某件物品有多件却不能装满背包的时候，一件一件的来做01背包 太浪费。然后採取二进制的办法，每次乘2。
完全背包：有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
多重背包，算是01和完全的结合体，这次运用上模板解题。 1：题目描述 http://acm.nyist.net/JudgeOnline/problem.php?pid=546 Divideing Je
1 01背包 2完全背包 3多重背包 4 123讲的综合 5二维费用的背包问题 6分组背包 7依赖性背包 8泛化物品 9一些变式
在使用一维数组解决 0-1 背包问题的基础上，讲解如何解决完全背包、多重背包、分组背包、背包具体方案 和 有依赖的背包问题 ...
这个背包，听起来就很麻烦的样子。别慌，只要你理解了前面的两种背包问题，拿下多重背包简直小菜一碟。
首先这是一道多重背包的裸题，题意在代码中的注释里有。多重背包就是所给的物品是有限的(任意个)，我们则可以把多重背包的问题转换成01背包和完全背包来求解。首先我们先把01背包和多重背包的过程封装成函数，需要用的时候传参过去就好了，然后我来解释一下什么时候用01背包，什么时候用完全背包。我们先不考虑价值，假如说A的重量是3，有10个，B的重量是5，有2个，而你的背包的最大重量为15。对于A来说，3*10=30，它大于你的背包的最大重量，可以夸张的当成A物品是有无限个的，因为在你背包重量的允许下A物品是想装多少就装多少的，这时候就把A物品当成完全背包来装，而B物品就需要当成两个01背包来装了。这就是多重背包的大致思路，当然对于多重背包还有一个二进制优化，因为如果一个物品在你的背包最大承重范围内的个数太多，这就要装好几次01背包，所以用二进制优化可以缩短同一物品使用01背包的次数。下面我就大致解释一下二进制优化过程。
01背包问题是所有背包问题的基础，之后的问题都可以在此基础之上变化，所以一定要理解清楚。尤其是对待不同问题，找出状态转移方程是解题的关键。
混合背包问题是把01背包、完全背包、多重背包混在一起的问题，看着比较复杂，其实就是分而治之，转换为前面这三种背包问题即可。
请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。
在众多背包问题中「01 背包问题」是最为核心的，因此我建议你先精读过 背包问题 第一讲 之后再阅读本文。
01背包 for(int i=0;i<n;i++) //遍历每一件物品 for(int j=v;j>=wei[i];j--)//遍历背包容量，表示在上一层的基础上，容量为J时，第i件物品装或不装的最优解; dp[j]=max(dp[j-wei[i]]+val[i],dp[j])； 初始化细节：装满dp[0]=0;其余赋值-INF；不装满全初始化为0； 完全背包 for(int i=0;i<n;i++) //遍历每一类物品 for(int j=wei[i];j<=v;j++)//遍历容量，此时代表第一
但对于「组内」物品而言，由于最多只能选一件物品，因此对于成本相同的多件物品，我们应当只保留价值最大的物品，从而让总的物品数量变少。
从状态定义我们发现，常规的分组背包问题对物品组的考虑是“线性“的（从前往后考虑每个物品组）。
之前我们已经体统的讲解了01背包和完全背包，如果没有看过的录友，建议先把如下三篇文章仔细阅读一波。
这是 LeetCode 上的「1449. 数位成本和为目标值的最大数字」，难度为 「困难」。
如果你还没看过，我十分建议你抽时间去学习一下。因为 路径问题 里教到的「经验解法」和「技巧解法」将会贯穿我们之后的所有「动态规划专题」系列。
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 24496 Accepted Submission(s): 8740
之前在做背包的题目时看到了这道题，一看，大喜，这不是裸裸的01背包吗！！ 然后华丽丽的超时，相信很多人也和我一样没有考虑到数据量的大小。
多重背包区别于01背包和完全背包的关键是，物品的个数一定。 但它们的状态方程还是一样的，对于多次背包问题，我们可以把他转换成01背包问题，但是要注意优化，因为当数据量比较大的时候，容易费时，即时间复杂度太高，需要进行优化。 我们先把之前的状态方程在· f[i][j]表示从i个物品中选取体积不超过j物品的最大价值。 f[i][j]=max(f[i-1][j],f[i-1][j-v]+w,f[i-1][j-2v]+2w,........,f[i-1][j-kv]+kw),kv<j。 这时读者朋友可能会想可不可以像完全背包那样，进行状态方程的转换。emmm，答案是：不可以的，不信的话可以自己尝试转换一下。 下面我们用01背包的思想去解决该问题，对于i个物品有k个，价值为w；那么我们可不可以把它这样理解：我们把这些物品都看成不一样的，再仔细想一下，这不就变成01背包了吗？但是时间太慢了，我们优化一下。 这里的优化为二进制优化 我们把这k个物品进行分割处理， 分为1，2，4，8，16………。只要保证其和大于k就可以。 为什么空2进制来优化呢，因为可以减少时间复杂度，其他0到k之中的任意一个数都可以由分割的二进制数进行组合而成。 例如：k为25，下面进行分割 1，2，4，8，16.怎么分割的呢？ 先是1，那么还剩24 2，22 4，28 8，20 16，4 4，0//剩余的自己组成一个 剩下就是01背包了，注意此时不再有i个物品了，而是变成了转换以后的物品个数。
本篇我们继续完成与 完全背包 相关的练习题，共三篇。本篇是第二篇，第一篇在 这里。
在上一题 322. 零钱兑换 中，我们求的是「取得特定价值所需要的最小物品个数」。
上一讲当中我们一起学习了动态规划算法中的零一背包问题，我们知道了所谓的零一背包是指每一种物品只有一个，所以它的状态只有0和1两种，即拿或者不拿。而今天我们要来讨论物品不止有一个的情况，物品不止有一个也分两种，一种是不作任何限制，要多少有多少，这种称为完全背包问题，另一种是依然有个数限制，这种称为多重背包问题。
本文内容基本涵盖了 dd_engi 的背包九讲，在此基础上加上了自己的理解和代码实现
题目是这样的：来源：https://www.acwing.com/problem/content/4/
算法工程师成长计划 近年来，算法行业异常火爆，算法工程师年薪一般20万～100 万。越来越多的人学习算法，甚至很多非专业的人也参加培训或者自学，想转到算法行业。尽管如此，算法工程师仍然面临100万的人才缺口。缺人、急需，算法工程师成为众多企业猎头争抢的对象。 计算机的终极是人工智能，而人工智能的核心是算法，算法已经渗透到了包括互联网、商业、金融业、航空、军事等各个社会领域。可以说，算法正在改变着这个世界。 下面说说如何成为一个算法工程师，万丈高楼平地起，尽管招聘启事的算法工程师都要求会机器学习，或数据挖
动态规划（英语：Dynamic programming，简称DP）是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题 动态规划思想大致上为：若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。 由于通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。
由于每个字符串只能被选一次，且每个字符串的选与否对应了「价值」和「成本」，求解的问题也是「最大价值」是多少。
将每个任务看作一个「物品」，完成任务所需要的人数看作「成本」，完成任务得到的利润看作「价值」。
从本篇开始，我们会完成三道与 完全背包 相关的练习题。会进入比较轻松的「完全背包」复习强化阶段 ~
理解成多重背包的同学主要是把m和n混淆为物品了，感觉这是不同数量的物品，所以以为是多重背包。
由于 LeetCode 没有与「分组背包求最大价值」相关的题目，因此我们使用「分组背包求方案数」来作为练习篇。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。 输出最大价值。
大学期间，ACM队队员必须要学好的课程有： l C/C++两种语言 l 高等数学 l 线性代数 l 数据结构 l 离散数学 l 数据库原理 l 操作系统原理 l 计算机组成原理 l 人工智能 l 编译原理 l 算法设计与分析 除此之外，我希望你们能掌握一些其它的知识，因为知识都是相互联系，触类旁通的。
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中， 可能会有很多可行解。没一个解都对应于一个值，我们希望找到具有最优值的解。胎动规划算法与分治法类似，其基本思想也是将待求解问题分解为若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适用于动态规划算法求解的问题，经分解得到的子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算很多次。如果我们能保存已解决子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解决的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划算法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。
背包问题可以说是一个老生常谈的问题，通常被用作面试题来考查面试者对动归的理解，我们经常说学算法，初学者最难理解的就是 “二归”，一个叫递归，另一个叫动归。
动态规划中比较经典一类问题是背包问题，而背包问题又会产生很多的变种，容易混淆的是，说起背包，有些人可能会想到贪心算法，其实贪心算法只能解决部分满足拟阵性质的背包问题，具体后面再提贪心算法。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出最大价值。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
从上图中可以看出，01背包每次计算i时的状态只用到了i-1的状态，所有可以舍去i这一维，优化成一维dp。
这是 LeetCode 上的「1049. 最后一块石头的重量 II」，难度为「中等」。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
对象存储
实时音视频
即时通信 IM
