背包问题中我们常见的就是 01背包和 完全背包。在leetcode的题库中主要就是这两种类型的题目。而完全背包又是也是01背包稍作变化而来，即：完全背包的物品数量是无限的。所以背包问题的基础就是01背包问题。完全背包问题请参考 动态规划之背包问题——完全背包。
题目链接：https://leetcode-cn.com/problems/partition-equal-subset-sum/
首先这是一道多重背包的裸题，题意在代码中的注释里有。多重背包就是所给的物品是有限的(任意个)，我们则可以把多重背包的问题转换成01背包和完全背包来求解。首先我们先把01背包和多重背包的过程封装成函数，需要用的时候传参过去就好了，然后我来解释一下什么时候用01背包，什么时候用完全背包。我们先不考虑价值，假如说A的重量是3，有10个，B的重量是5，有2个，而你的背包的最大重量为15。对于A来说，3*10=30，它大于你的背包的最大重量，可以夸张的当成A物品是有无限个的，因为在你背包重量的允许下A物品是想装多少就装多少的，这时候就把A物品当成完全背包来装，而B物品就需要当成两个01背包来装了。这就是多重背包的大致思路，当然对于多重背包还有一个二进制优化，因为如果一个物品在你的背包最大承重范围内的个数太多，这就要装好几次01背包，所以用二进制优化可以缩短同一物品使用01背包的次数。下面我就大致解释一下二进制优化过程。
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
之前我们已经体统的讲解了01背包和完全背包，如果没有看过的录友，建议先把如下三篇文章仔细阅读一波。
首先完全背包问题需要01背包问题做铺垫,如果读者01背包问题没有解决,一定要理解之后,在看完全背包问题,包括01背包的优化! 这里是01背包 这里是01背包的全部优化
请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。
所有数的总和为sum，假设加法的总和为x，那么可以推出x = (S + sum) / 2。
有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。
已知:有一个容量为V的背包和N件物品，第i件物品最多有Num[i]件，每件物品的重量是weight[i]，收益是cost[i]。
如果你还没看过，我十分建议你抽时间去学习一下。因为 路径问题 里教到的「经验解法」和「技巧解法」将会贯穿我们之后的所有「动态规划专题」系列。
动态规划需要搞定三个系列：三个背包，零钱问题和股票问题。今天就开始干掉三个背包问题。
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++)//遍历容量，此时代表第一
题目是这样的：来源：https://www.acwing.com/problem/content/4/
将每个任务看作一个「物品」，完成任务所需要的人数看作「成本」，完成任务得到的利润看作「价值」。
题目链接：https://leetcode-cn.com/problems/last-stone-weight-ii/
今天我们就来说一说滚动数组，其实在前面的题目中我们已经用到过滚动数组了，就是把二维dp降为一维dp，一些录友当时还表示比较困惑。
背包问题其实有很多细节，如果了解个大概，然后也能一气呵成把代码写出来，但稍稍变变花样可能会陷入迷茫了。
Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0. If there are multiple solutions, return any subset is fine. 题目意思也很简单，给出一个不含重复数字的数组，找到最长的一个子数组，子数组里的元素必须两两整除。 这里有个很简单的数学性质，就是整除的传递性，如果a%b==0 且 b%c == 0，那么a%c == 0，说白了如果c是b的因子，b又是a的因子，那么c肯定是a的因子。这样我们就可以在数组中找出很多整除链（a->b->c->d，其中b是a的因子，c是b的因子，d是c的因子），这样的链条就满足两两整除的条件，题目就变成了求最长的链条。 先上代码，然后我再解释下我的代码。
题目链接：https://leetcode-cn.com/problems/target-sum/
看完前面四篇关于背包问题的文章，你会发现背包问题其实也不过如此，而且它们之间有很多相似的地方，本篇文章就来揭开它们面纱，将背包问题彻底搞定。
这是 LeetCode 上的「1449. 数位成本和为目标值的最大数字」，难度为 「困难」。
背包问题的经典资料当然是：背包九讲。在公众号「代码随想录」后台回复：背包九讲，就可以获得背包九讲的pdf。
有N件物品和一个最多能被重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
01背包问题是所有背包问题的基础，之后的问题都可以在此基础之上变化，所以一定要理解清楚。尤其是对待不同问题，找出状态转移方程是解题的关键。
去了新的环境学习，感觉还可以，当然因为期末刚结束的原因，导致这段时间有点松懈，后天就要回家了，还是非常开心的。
动态规划问题是学习算法时一个尤为重要的内容，在讲解什么是动态规划之前，首先来讲一下分而治之。
先来理解一下题意，假如你来到了一个藏宝洞前，然后手里有一个背包，面前有很多金银珠宝，数量为 n，而你的背包容量有限为 v，你想怎么装，价值最大。
在上一题 322. 零钱兑换 中，我们求的是「取得特定价值所需要的最小物品个数」。
在C/C++中，可以使用动态规划来解决01背包问题。动态规划是一种常用的解决优化问题的算法思想，它通过将问题分解为子问题，并利用子问题的解来构建更大规模的问题的解。
背包问题的经典资料当然是：背包九讲。在公众号「代码随想录」后台回复：背包九讲，就可以获得背包九讲的PDF。
本题背景有意思，大家当乐子看，目前没有找到题目原题，也没有写过完全是01背包模板的题目，该篇文章大家注意其01背包一维写法的模板就好，注意各个关键点
1 01背包 2完全背包 3多重背包 4 123讲的综合 5二维费用的背包问题 6分组背包 7依赖性背包 8泛化物品 9一些变式
已知:有一个容量为V的背包和N件物品，第i件物品的重量是weight[i]，收益是cost[i]。
多重背包，算是01和完全的结合体，这次运用上模板解题。 1：题目描述 http://acm.nyist.net/JudgeOnline/problem.php?pid=546 Divideing Je
背包问题实际上是动态规划的一种经典应用，本文想通过介绍一种模板用于解决各种背包问题。
01背包的原型就是有N件物品和一个容量为V的背包。放入第i件物品耗费的空间是Ci，得到的价值是Wi，求将哪些物品装入背包可使获得的价值总和最大。而这道题的题意也就是这个意思，01背包的特点就是每种物品仅有一件，可以选择放或者不放。
在众多背包问题中「01 背包问题」是最为核心的，因此我建议你先精读过 背包问题 第一讲 之后再阅读本文。
动态规划是我最早接触的算法，一开始非常简单，固定模板题，后来愈发愈发难起来了，条件，状态压缩等等，难点主要是，状态怎么表示，状态转移方程怎么写，这篇文章将会从背包五大问题详解，希望能帮助到大家去类比，思考其他动态规划题目。
饭卡 Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 28562 Accepted Submission(s): 9876 Problem Description 电子科大本部食堂的饭卡有一种很诡异的设计，即在购买之前判断余额。如果购买一个商品之前，卡上的剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负），否则无法购买（即
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 24496 Accepted Submission(s): 8740
题目 有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
因为这个优化十分简单，代码实现不难，且优化的时间只是常数级别的，故不给出我的理解和代码。
在上一篇中，我们对01背包问题进行了比较深入的研究，这一篇里，我们来聊聊另一个背包问题：完全背包。
有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
01背包问题，是用来介绍动态规划算法最经典的例子，网上关于01背包问题的讲解也很多，我写这篇文章力争做到用最简单的方式，最少的公式把01背包问题讲解透彻。
要求的是“总价值最小”“总件数最小”，只需简单的将上面的状态转移方程中的max改成min即可。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
对象存储
实时音视频
即时通信 IM
