钓鱼网站实施过程,wordpress更换皮肤,招聘网站建设方案,找别人做网站一般注意什么前言#xff1a;
好久没写0-1背包问题了#xff0c;都有些不记得了#xff0c;写这篇文章给自己以后做简单参考#xff0c;如果能同时帮到读者#xff0c;不胜荣幸。
正文
0-1背包问题是这样的一个问题#xff0c;假设有一个背包#xff0c;其容量为 capacity 。在地…前言
好久没写0-1背包问题了都有些不记得了写这篇文章给自己以后做简单参考如果能同时帮到读者不胜荣幸。
正文
0-1背包问题是这样的一个问题假设有一个背包其容量为 capacity 。在地上有一堆物品其数量为 n 每个物品有两种属性重量 w和价值 v。
要求就是找到一个物品的组合使得它们的重量小于等于最大容量并且其价值最大。
动态规划的思路解0-1背包问题
首先建立一个二维数组dp其中dp[i][j]表示仅使用前i个物品的情况下当背包容量为j时所能获得的最大价值。也即从前i个物品里面选取一些物品这些物品的总重量小于等于j但是它们的价值之和最大这个最大价值和就记为dp[i][j]。
dp的行宽为n表示总共有n个物品列宽为capacity表示背包的最大容量为capacity。
大致是这样 假设有n个物品并用1-n分别给各个物品编号wivi分别表示第i个物品的重量和价值。
那么第一行的第j列表示当仅使用物品1、背包容量为j时所能装进背包里面的最大价值。
所以在第一行当中
1若w1 j那么背包容量j是无法容纳第一个物品的重量的此时应填0
2若w1 j那么背包容量是可以容下第一个物品的重量的此时应填v1.
所以第一行的元素只能填0或者v1而且前半段是0后半段是v1
假设n10背包容量为3最终容量
1,2,3各个物品的编号
2,7,1各个物品的重量
1,2,3各个物品的价值
假设w17那么第一行如下 设i1那么对于第i行的第j列应该这么填
1wi j时那么即使把背包里面已经装进去的东西全部腾空也不足以装下第i个物品。
此时dp[i][j] dp[i-1][j]。也就是说考虑前i个物品和前i-1个物品是一样的结果。
2wi j时可以考虑把第i个物品放进去 2-1假如要把第i个物品放进去那么第i个物品会占据wi的容量剩下的容量最大能装多少价值的物品呢毫无疑问应该最大能装dp[i-1][j-wi]的价值这是因为dp[m][n]就表示仅使用前m个物品在容量为n时所能装入的最大价值。也即dp[i][j] dp[i-1][j-wi] vi。 2-2假如不把第i个物品放进去那么价值总量维持不变也即dp[i][j] dp[i-1][j]。 (2-3) 那到底要不要把第i个物品放进去呢有人可能会说既然能放进去那为什么不放进去呢 放进去的话价值不是更大吗事实上不一定因为这里所说的能放进去是指把背包里面 已经放进去的东西腾空后第i个物品能放进去。但是强行把第i个物品放进去之后有可能 导致原来已经放进去的某些物品被挤得没有空间放了这就有可能导致总价值量的减小。 所以当wi j时dp[i][j] max{dp[i-1][j-wi] vi , dp[i-1][j]}
所以最终填表就是 所以从表格中可以看出来当背包容量为3物品个数为3
各个物品编号为1,2,3
各个物品重量为2,7,1
各个物品价值为1,2,3时
能装进背包里面的最大价值为4表格右下角的数 练习
这张图片是力扣上面的题目也是0-1背包问题 写在最后如有错误敬请指正礼貌交流感激不尽。
