一、计算机算法分析考试:动态规划0-1背包问题,怎么算
问题描述：
给定n种物品和一背包，物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品（物品不能分割），使得装入背包中物品的总价值最大?
抽象描述如下：
x[n]:表示物品的选择，x[i]=1表示选择放进物品i到背包中。
问题分析：
1.抽象之后背包问题转换为找到一个最优的数组，x1，x2，.....,xn的0-1序列。
2.假设最优解的序列为x1，x2，.....,xn，能使背包容量C的总价值最大.
如果，x1=1，则x2,...,xn是C-w1容量的背包的总价值依然是最大的序列；
如果，x1=0，则x2,....,xn是C容量的背包的总价值依然是最大的序列。
这就是我们所说的最优子结构性质。
3.进一步分析：我们用m(i,j)表示为已经判断好了1:i-1的序列的背包最大价值，并且此时的背包剩余的容量为j，对物品i进行判断
如果j>wi,就只要做出选择wi和不选择wi情况下，哪种更能使背包的总价值更大：m(i,j)=max{ m(i+1,j),m(i+1,j-wi)+vi}(注意这是个递归式)
如果j<wi:m(i,j)=m(i+1,j)
初始化：m(n,j)=vn(j>= wn)；
m(n,j)=0(0<=j< wn)
m(0,C)=0
最终的结果：m(1,C）
4.依次我们就得到了一个递归的表达式：
5.如果单纯的从利用递归，重复计算了很多的值，耗费的时间是很大的，动态规划还需避免这种重复计算，怎样自顶向下或自底向上的计算呢？
采用列表的方法就可以很好的分析设计自顶向下或自底向上的计算的算法了
举例分析：
n=3,c=6,w={4,3,2} v={5,2,1}
m[i][j]=max{ m[i+1][j], m[i+1][j-w[i]]+v[i]}
列表如下：
最左边箭头：我们计算的方向，从第3行开始向上计算法值。
表中红色箭头是我们通过选择做出的结果：列如 m[2][3]=max{m[3][3],m[3][3-w[2]]+v[2]}，我们最终选择了m[3][3-w[2]]+v[2]。
整个问题的最优解保存在m[1][6]中。
二、背包问题和0-1背包问题有什么区别
背包问题和0－1背包问题区别为：循环变量不同、约束条件不同、最大总价值不同。
一、循环变量不同
1、背包问题：背包问题须先求出列坐标j较小的元素，故让循环变量j的值从小到大递增。
2、0－1背包问题：0－1背包问题须先求出列坐标j较大的元素，故让循环变量j的值从大到小递减。
二、约束条件不同
1、背包问题：背包问题的约束条件是给定几种物品，物品可以取无限次。
2、0－1背包问题：0－1背包问题的约束条件是给定几种物品，物品只可以取一次。
三、最大总价值不同
1、背包问题：背包问题若取了1件第i个物品，则总容量变为j－W［i］，剩下的仍可以在前i件物品中去取，其最大总价值为B［i］［j－W［i］］＋ P［i］。
2、0－1背包问题：0－1背包问题若取了1件第i个物品，则总容量变为j－W［i］，剩下的只能在前i－1件物品中去取了，其最大总价值为B［i－1］［j－W［i］］＋ P［i］。
三、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表示好了。
m(1,2,3,4....i-1)(w)====(书写方便)>m(i-1)(w)，这样上面的状态转移方程就出来。
m(i)(W)= max( m(i-1)(W- weight(i))+value(i), m(i-1)(w))
这样，状态的转移方程就出来。这里不得不说下，网上的其他教程这一点上说的不够仔细，上来就搞一个
f[i-1][j]= max(f[i-1][j-w(i)]+value[i],f[i-1][j])。谁看的懂啊。
这里我们针对上面的数值给出具体的求解过程。首先给出物品的函数值。
weight(1)= 2,value(1)= 6,
weight(2)= 2,value(2)= 3,
weight(3)= 6,value(3)= 5,
weight(4)= 5,value(4)= 4,
weight(5)= 4,value(5)= 6,
那么最大值函数
m(1)(1)= 0；物品重量为2.
m(1)(2)= 6,物品恰好放入背包。
m(1)(3)= 6，m(1)(4)= 6...，只有1号物品，最大值只能为6。现在考虑有第2件物品的情况，现在有两件物品，m函数表示为
m(1,2)(w)。
根据之前所说 1），如果不把2号物品放入，那问题回到只有1号物品的情况
那么
m(1)(1)= 0,1号物品放不进，
m(1)(2)= 6, 1号物品放进背包。
m(1)(3)= 6, 1号物品放进容量为3的背包
m(1)(4)= 6, 1号物品放进容量为4的背包。
根据之前所说2），把2号物品放入，此时需要 1号物品在背包容量w减去2号物品的容量weight(2),即 w-2的问题。
m(1)(1- 2)= 0,显然，此时背包总容量为1，还有减去2号物品的容量2，1-2=-1，显然放不进去。
m(1)(2- 2)= 0,显然，背包的容量减去2号物品的容量后，没有剩余，就是说只能放2号物品，此时背包的最大值
m(1,2)(2) = max(m(1,2)(2-2)+value(2), m(1)(2))= max(0+3,6)= 6。就是说，在有1,2两件物品，背包容量为2的情况下，最大值为6。
继续考虑背包容量为3，第一种情况的已经讨论。现在讨论第二种情况，把2号物品放入背包，就要剩下w-2的容量给1号了。
m(1,2)(w-2)= m(1,2)(3-2)=m(1,2)(1) = 0, value(2)= 3因此，
m(1,2)(3)= max[ m(1,2)(3-2)+value(2),m(1)(3)] = max(0+3,6)= 6。
继续考虑背包容量为4，同理，第一种情况讨论，只讨论第二种情况，把2号物品放入背包，就要剩下w-2的容量给1号了。
m(1,2)(4-2)=m(1,2)(2)=6,value(2)= 3
m(1,2)(4)= max[ m(1,2)(4-2)+value(2),m(1)(4)]=max[m(1,2)(2)+value(2),m(1)(4)]= max(6+3,6)= 9;
此时m(1,2)(4)= 9;之后，背包容量为5，6,7，。的时候，1,2物品都放进去，最大值不再改变，都是9
m(1,2)(5)= 9，m(1,2)(6)= 9，m(1,2)(7)= 9，m(1,2)(8)= 9
同理，weight(3)= 6,value(3)=5
m(1,2,3)(1)= max[ m(1,2,3)(1-6)+value(3),m(1,2)(1) ]= 0
m(1,2,3)(2)= max[ m(1,2,3)(2-6)+value(3),m(1,2)(2) ]=6
m(1,2,3)(3)= max[ m(1,2,3)(3-6)+value(3),m(1,2)(3) ]=6
m(1,2,3)(4)= max[ m(1,2,3)(4-6)+value(3),m(1,2)(4) ]=9
m(1,2,3)(5)= max[ m(1,2,3)(5-6)+value(3),m(1,2)(5) ]=9
m(1,2,3)(6)= max[ m(1,2,3)(6-6)+value(3),m(1,2)(6) ]= 9
m(1,2,3)(7)= max[ m(1,2,3)(7-6)+value(3),m(1,2)(7) ]= max[m(1,2,3)(1)+5,9]= max[0+5,9]=9
m(1,2,3)(8)= max[ m(1,2,3)(8-6)+value(3),m(1,2)(8) ]= max[m(1,2,3)(2)+5,9]= max[6+5,9]=11;
剩下的推导都是如此，根据背包容量一步一步的推导即可。
文章到此结束，希望我们对于九种0-1 背包问题详解_0-1背包问题的问题能够给您带来一些启发和解决方案。如果您需要更多信息或者有其他问题，请随时联系我们。
