动态规划01背包问题背包问题( 二 )

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;
剩下的推导都是如此，根据背包容量一步一步的推导即可。
三种基本背包问题问题描述：有n件物品和容量为m的背包给出i件物品的重量以及价值求解让装入背包的物品重量不超过背包容量且价值最大。
特点: 这是最简单的背包问题，特点是每个物品只有一件供你选择放还是不放。
① 二维解法
设f[i][j]表示前 i 件物品总重量不超过 j 的最大价值可得出状态转移方程
f[i][j]=max{f[i-1][j-a[i]]+b[i], f[i-1][j]}
在一些情况下题目的数据会很大因此f数组不开到一定程度是没有办法ac 。
②一维解法
设f[j]表示重量不超过j公斤的最大价值可得出状态转移方程
f[j]=max{f[j], f[j?a[i]]+b[i]}
问题描述：有n件物品和容量为m的背包给出i件物品的重量以及价值求解让装入背包的物品重量不超过背包容量且价值最大。
特点：题干看似与01一样但它的特点是每个物品可以无限选用。
设f[j]表示重量不超过j公斤的最大价值可得出状态转移方程
f[j] = maxj{f[j], f[j?a[i]]+b[i]}
问题描述：有n件物品和容量为m的背包给出i件物品的重量以及价值还有数量求解让装入背包的物品重量不超过背包容量且价值最大。
特点：它与完全背包有类似点特点是每个物品都有了一定的数量。
状态转移方程为：
f[j] = max{f[j], f[j?k?a[i]]+k?b[i]}
题目一：
链接：力扣（LeetCode）
题目：给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

动态规划01背包问题 背包问题( 二 )

秒懂生活扩展阅读

动态规划01背包问题背包问题( 二 )