动态规划01背包问题背包问题

背包问题（完全背包）1.矩阵链乘法
2.投资组合问题
3.完全背包问题
4.01背包问题
5.最长公共子序列
一个背包，可以放入n种物品，物品j的重量和价值分别为，如果背包的最大重量限制是b，怎么样选择放入背包的物品以使得背包的总价值最大？
组合优化问题，设表示装入背包的第j个物品的数量，解可以表示为。那么目标函数和约束条件是：
如果组合优化问题的目标函数和约束条件都是线性函数，称为线性规划。如果线性规划问题的变量都是非负整数，则称为整数规划问题。背包问题就是整数规划问题。限制所有的时称为0-1背包
子问题的界定（就是靠什么来划分子问题）：由参数k和y界定
k：考虑对物品1,2,3,...,k的选择。
y：表示背包总重
子问题计算顺序：k=1,2,...,k，对给定的k，y=1,2,...,b
：装前k个物品，重量不超过y时的背包最大值。
包含两种情况：不装第k种物品或至少装一件第k种物品。
对的解释：装一件第k种物品后，最优的解法仍然是在前k个物品进行选择，仍有可能再选入1件第k种物品。
对边界条件:
：即只用第一种物品背包重量限制为y的最大价值，为了保证背包不超重，第一种物品至多能装个，因为背包价值为
有些那么通过设置为负无穷，在选择过程中抛弃掉为负的情况。
标记函数：用来追踪解
按照递推公式：以k=2为例子，简单演算如下：
依次类推，可得备忘录表：
标记函数的备忘录：
物品受限背包：第i种物品最多用个
0-1背包问题：
多背包：m个背包，背包装入最大重量在满足所有背包重量约束下使物品价值最大。
二维背包：每件物品重量和体积，背包总重不超过b，体积不超过V，使得物品价值最大。
此问题是完全背包问题，即一个物品可重复出现。
0-1背包问题入门详解网上好多关于背包问题的解释，自己也看了，感觉解释的不容易通俗易懂，所以自己来写一个非常容易懂得。
0-1背包问题说的是，给定背包容量W，一系列物品{weiht,value}，每个物品只能取一件，获取最大值。
采用动态规划求解，动态规划的一般规律都是，
在什么什么前i个状态下的最大值或者最小值的前提下，然后再把i的状态的值求出来。
这里我们定义一个函数，表示状态。
m(1,2,3,4..i)(w)表示有1号,2号,3号,4号....i号物品，背包容量为w的时能够取得的最大值。举例说明，
假设1，2,3,4,5号物品，它们的重量分别是2,2,6,5,4，用weight(i)表示，它们的价值分别是6,3,5,4,6用value(i)表示
m(1)(1)表只有1号物品，背包容量为1的时候，最大值。显然，
m(1)(1) = 0，因为背包容量小于2，所以最大值为0 。
m(1)(2) = 6, 此时背包容量等于2，装下1号物品，最大值为6，接下来
m(1)(3) = 6,m(1)(4) = 6，...m(1)(..) = 6,因为只有一件物品，最大为6 。
m(1,2)(1),m(1,2)(2),m(1,2)(3)表示有物品1号，2号，背包容量分别为1,2,3的时候最大值。
最大值和物品的数量相关，也和背包容量相关。
这里必须强调一下，m(1,2,3,...i)(w) 表示有1,2,3,4....i，这么多物品可选，未必全部装进去的情况下(受限于w)的最大值。
接下来讨论在1,2,3.....i物品的最大值。对于第i件物品，背包容量为W，有两种情况，
1）不把第i件物品装进背包，那么此时，只有1,2,3,4,,,,i-1件物品，背包的最大值是m(1,2,3,4,5....i-1)(W) 。此时，不管W多么大，即使和宇宙一样大，背包里的价值之和1,2,3,4,5..i-1这些物品相关。
2）把第i件物品装进去。既然把i件物品装进背包，那么1,2,3,4.....i-1物品只能占用 W-weight(i) 这么多重量了。这个时候，
之前的1,2,3,4......i-1物品在背包容量为（W-weight(i)）下的最大值为m(1,2,3.......i-1)[ W - weight(i) ] 。
此时背包的最大值就是第i件物品的价值value(i)加上
前1,2,3,4....i-1件物品在背包容量为（W-weight(i) 下的最大值m(1,2,3.......i-1)[ W - weight(i) ]
m（1,2,3,4.......i-1,i)(W)= m(1,2,3.......i-1)[ W - weight(i) ] +value(i) ;
然后我们比较一下，情况1）2）的最大值就可以了即
m(1,2,3,4....i-1,i)(W) = max[m(1,2,3.......i-1)[ W - weight(i) ] +value(i) , m(1,2,3,4,5....i-1)(W) ] 。
这里有人会说，前1,2,3,4.....i-1件物品在W-weight或者W的容量下怎么求啊。
这里就说到动态规划的点上。动态规划有点数学归纳法的感觉，不过是从后向前推到，要求解i，先求解i-1,；要求解i-1，先求解i-2，这样一步一步到2,1 。因此需要给定初始状态。我们一直用1,2,3,4.....i-1表示前i-1件物品，太麻烦，直接用i-1表示好了。

动态规划01背包问题 背包问题

秒懂生活扩展阅读

动态规划01背包问题背包问题