2023年8月1日发(作者：)

⼀⽂彻底搞懂01背包算法0-1 背包问题：给定 n 种物品和⼀个容量为 C 的背包，物品 i 的重量是 ，其价值为 。问：应该如何选择装⼊背包的物品，使得装⼊背包中的物品的总价值最⼤？假设⼀个函数B是求解总价值的函数，有两个因变量n与C ;则我们的优化⽬标就变为

展开公式其实就是：

x的取值范围为0或者1，代表着这个物品我们可以选择拿或者不拿，我们想要找出这样的01组合如： 使得 最⼤。

我们假设⼀个函数也就是说B函数是⼀个能够⾃动组合x的取值使得 达到最⼤。

再次理解这个 这个函数的意义：从n个物品⾥⾯选物品，容量为C,能达到的最⼤价值。如何求解这个函数呢？我们可以细分⽬标，试想⼀下，如果想要在5个商品⾥⾯选择，得到最⼤总价值，那么肯定得先求得在4个物品⾥⾯选择，得到最⼤价值后，然后考虑第五个物品要不要放进去？放进去会不会超过容量限制，会不会得到⼀个最⼤价值。我们就得到了⼀个函数。这⾥存在⼀个困扰：如果有多余空间去放置的话,那么放置肯定⽐不放的价值⼤啊，因为我多放⼊⼀个物品了啊，也就是说选择不放的函数肯定⼩与放置的函数 ,说道这⾥你就犯了⼀个惯性错误，认为 与 所对应的 中的 组合相同，在理解这个函数的意义：从n个物品⾥⾯选物品，容量为C,能达到的最⼤价值。这个两个函数组合不⼀定相同，为容量C约束条件变了。就会变为从n-1个物品⾥⾯选，容量为C与从n-1个物品⾥⾯选，容量为c-w且加上v,两者哪个⼤。彻底理解了函数B之后，我相信没有什么能够阻挡你学习这个算法了。

例：

解：B(2,2)为最⼤价值，如果我们拿最后物品w=2,v=2,因为w=2=c,所以我们可以选择拿或者不拿

1、拿：如果确定拿⾛最后⼀个物品，则B(2,2)=B(2-1,2-2)+2=B(1,0)+2

2、不拿：如果确定不拿⾛最后⼀个物品，则B(2,2)=B(1,2);因为最后⼀个物品我选择不拿，所以情景肯定变为从1个物品⾥⾯选，容量为2，是否达到最⼤值，因此等式左右两边相等。

然后⽐较 与 哪个⼤，很明显，对于B(1,0),已经没有容量去放置下⼀个物品，就相当于从0个物品⾥⾯选 则.求解 ,代表着我只能去选择（第⼀件：2=1，v=1）的我要不要去拿，肯定得拿啊，再不拿就没东西可以拿了，结果为0，拿了话结果价值就为1 显然这是个递归求解的过程，实现递归过程，并测试⼀下capicaty=[0,1,2]value=[0,1,2]def best_value(i,j): if i==0: return 0 if j-capicaty[i]<0: return best_value(i-1,j) else: return max(best_value(i-1,j),best_value(i-1,j-capicaty[i])+value[i]) print(best_value(2,2)) result:2

递归结果正确，但是如果数据量⽐较⼤的话，程序肯定会变的缓慢，递归会使得程序效率变差这个原因我就不解释了，但是如果我要求B(2,2)是不是要计算，B(1,2),B(0,2),如果要求B(1,2)是不是得求⼀下B(0,2)，最后才能返回结果，我们是不是重复计算了B(1,2)与B(0,2)。如果要是能把每个计算的结果保存下来，下次就不必重复计算了，可以的，我们把递归转化为递推。

声明⼀个矩阵maxvalue[N][C]，专门⽤来存放B函数的缓存结果，利⽤⾏列进⾏索引值，⾏代表有⼏个物品，列代表容量，这样的话如果要求B(2,2),就去索引第⼆个物品，容量为2 即maxvalue[2][2],找到这个值就ok了maxvalue=[[0 for i in range(3)] for j in range(3)]for k in range(1,3): for c in range(1,3): if c-capicaty[k]>=0: maxvalue[k][c]=max(maxvalue[k-1][c],maxvalue[k-1][c-capicaty[k]]+value[k]) else: maxvalue[k][c]=maxvalue[k-1][c]

B(2,2)那么我们去索引，maxvalue[2][2]同样得到2的结果,这样的话这个算法你就掌握了，可以去到动态规划的世界玩耍⼀番，好好感悟⼀下，晦涩难懂的理论知识，状态，状态转移⽅程，把⽬标划分为⼦⽬标，分⽽治之，你会发现你看得懂了，完美。

2023年8月1日发(作者：)

⼀⽂彻底搞懂01背包算法0-1 背包问题：给定 n 种物品和⼀个容量为 C 的背包，物品 i 的重量是 ，其价值为 。问：应该如何选择装⼊背包的物品，使得装⼊背包中的物品的总价值最⼤？假设⼀个函数B是求解总价值的函数，有两个因变量n与C ;则我们的优化⽬标就变为

展开公式其实就是：

x的取值范围为0或者1，代表着这个物品我们可以选择拿或者不拿，我们想要找出这样的01组合如： 使得 最⼤。

我们假设⼀个函数也就是说B函数是⼀个能够⾃动组合x的取值使得 达到最⼤。

再次理解这个 这个函数的意义：从n个物品⾥⾯选物品，容量为C,能达到的最⼤价值。如何求解这个函数呢？我们可以细分⽬标，试想⼀下，如果想要在5个商品⾥⾯选择，得到最⼤总价值，那么肯定得先求得在4个物品⾥⾯选择，得到最⼤价值后，然后考虑第五个物品要不要放进去？放进去会不会超过容量限制，会不会得到⼀个最⼤价值。我们就得到了⼀个函数。这⾥存在⼀个困扰：如果有多余空间去放置的话,那么放置肯定⽐不放的价值⼤啊，因为我多放⼊⼀个物品了啊，也就是说选择不放的函数肯定⼩与放置的函数 ,说道这⾥你就犯了⼀个惯性错误，认为 与 所对应的 中的 组合相同，在理解这个函数的意义：从n个物品⾥⾯选物品，容量为C,能达到的最⼤价值。这个两个函数组合不⼀定相同，为容量C约束条件变了。就会变为从n-1个物品⾥⾯选，容量为C与从n-1个物品⾥⾯选，容量为c-w且加上v,两者哪个⼤。彻底理解了函数B之后，我相信没有什么能够阻挡你学习这个算法了。

例：

解：B(2,2)为最⼤价值，如果我们拿最后物品w=2,v=2,因为w=2=c,所以我们可以选择拿或者不拿

1、拿：如果确定拿⾛最后⼀个物品，则B(2,2)=B(2-1,2-2)+2=B(1,0)+2

2、不拿：如果确定不拿⾛最后⼀个物品，则B(2,2)=B(1,2);因为最后⼀个物品我选择不拿，所以情景肯定变为从1个物品⾥⾯选，容量为2，是否达到最⼤值，因此等式左右两边相等。

然后⽐较 与 哪个⼤，很明显，对于B(1,0),已经没有容量去放置下⼀个物品，就相当于从0个物品⾥⾯选 则.求解 ,代表着我只能去选择（第⼀件：2=1，v=1）的我要不要去拿，肯定得拿啊，再不拿就没东西可以拿了，结果为0，拿了话结果价值就为1 显然这是个递归求解的过程，实现递归过程，并测试⼀下capicaty=[0,1,2]value=[0,1,2]def best_value(i,j): if i==0: return 0 if j-capicaty[i]<0: return best_value(i-1,j) else: return max(best_value(i-1,j),best_value(i-1,j-capicaty[i])+value[i]) print(best_value(2,2)) result:2

递归结果正确，但是如果数据量⽐较⼤的话，程序肯定会变的缓慢，递归会使得程序效率变差这个原因我就不解释了，但是如果我要求B(2,2)是不是要计算，B(1,2),B(0,2),如果要求B(1,2)是不是得求⼀下B(0,2)，最后才能返回结果，我们是不是重复计算了B(1,2)与B(0,2)。如果要是能把每个计算的结果保存下来，下次就不必重复计算了，可以的，我们把递归转化为递推。

声明⼀个矩阵maxvalue[N][C]，专门⽤来存放B函数的缓存结果，利⽤⾏列进⾏索引值，⾏代表有⼏个物品，列代表容量，这样的话如果要求B(2,2),就去索引第⼆个物品，容量为2 即maxvalue[2][2],找到这个值就ok了maxvalue=[[0 for i in range(3)] for j in range(3)]for k in range(1,3): for c in range(1,3): if c-capicaty[k]>=0: maxvalue[k][c]=max(maxvalue[k-1][c],maxvalue[k-1][c-capicaty[k]]+value[k]) else: maxvalue[k][c]=maxvalue[k-1][c]

B(2,2)那么我们去索引，maxvalue[2][2]同样得到2的结果,这样的话这个算法你就掌握了，可以去到动态规划的世界玩耍⼀番，好好感悟⼀下，晦涩难懂的理论知识，状态，状态转移⽅程，把⽬标划分为⼦⽬标，分⽽治之，你会发现你看得懂了，完美。