2023年8月1日发(作者：)
python动态规划背包问题算法_01背包问题（动态规划算法）P01: 01背包问题题⽬给定 N 种物品和⼀个容量为 V 的背包，物品 i 的体积是 wi，其价值为 ci 。(每种物品只有⼀个)问：如何选择装⼊背包的物品，使得装⼊背包中的物品的总价值最⼤？⾯对每个物品，我们只有选择放⼊或者不放⼊两种选择，每种物品只能放⼊⼀次。我们⽤之前同样的思路来⾛⼀遍试试假设只剩下最后⼀件物品，我们有两种选择1.剩余空间⾜够时，选择放⼊2.剩余空间不⾜时，不放⼊所以我们有两个最优的⼦结构：1.容量为V的背包放⼊i-1件物品的最优选择2.容量为V-w[i]的背包放⼊i-1件物品的最优选择所以，综合起来就是：i 件物品放⼊容量为V的背包的最优选择：max(容量为V的背包放⼊i-1件物品的最优选择，容量为V-w[i]的背包放⼊i-1件物品的最优选择+c[i])我们⽤f[i] [v]表⽰前 i 件物品放⼊容量为 v 的背包中可以获得的最⼤价值。⽤⼦问题定义状态：其状态转移⽅程是：f[i] [v] = max{f[i-1] [v],f[i-1] [v-w[i]]+c[i]}。我们先假设背包总容量为V = 12物品的容量数组为 w = [4, 6, 2, 2, 5, 1]价值数组为 c = [8, 10, 6, 3, 7, 2]f(i,v) = 0 (i<=1, vf(i,v) = c[0] (i==1, v>=p[0]);f(i,v) = f(i-1,v) (i>1, vf(i,v) = max(f(i-1,v), f(i-1,v-w[i-1])+c[i-1])(i>1, v>=w[i-1])我们每次从左⾄右，保存前⼀次的数据从上⾄下时，保存前⼀⾏的数据所以我们总的来说只⽤保存⼀⾏的数据，空间复杂度为O(V)时间复杂度为O(N*V),空间复杂度为O(V);但是，如果我们⽤原始的递归办法去做，即排列组合的⽅法去做时时间复杂度为O(2^N);那么当V很⼤，N较⼩时，⽐如V=1000，N=6时，⽤递归只⽤计算2^6=64次，⽽备受推崇的动态规划就需要计算1000*6=6000次所以说，算法没有绝对的好坏，关键要看应⽤的惨景
2023年8月1日发(作者：)
python动态规划背包问题算法_01背包问题（动态规划算法）P01: 01背包问题题⽬给定 N 种物品和⼀个容量为 V 的背包，物品 i 的体积是 wi，其价值为 ci 。(每种物品只有⼀个)问：如何选择装⼊背包的物品，使得装⼊背包中的物品的总价值最⼤？⾯对每个物品，我们只有选择放⼊或者不放⼊两种选择，每种物品只能放⼊⼀次。我们⽤之前同样的思路来⾛⼀遍试试假设只剩下最后⼀件物品，我们有两种选择1.剩余空间⾜够时，选择放⼊2.剩余空间不⾜时，不放⼊所以我们有两个最优的⼦结构：1.容量为V的背包放⼊i-1件物品的最优选择2.容量为V-w[i]的背包放⼊i-1件物品的最优选择所以，综合起来就是：i 件物品放⼊容量为V的背包的最优选择：max(容量为V的背包放⼊i-1件物品的最优选择，容量为V-w[i]的背包放⼊i-1件物品的最优选择+c[i])我们⽤f[i] [v]表⽰前 i 件物品放⼊容量为 v 的背包中可以获得的最⼤价值。⽤⼦问题定义状态：其状态转移⽅程是：f[i] [v] = max{f[i-1] [v],f[i-1] [v-w[i]]+c[i]}。我们先假设背包总容量为V = 12物品的容量数组为 w = [4, 6, 2, 2, 5, 1]价值数组为 c = [8, 10, 6, 3, 7, 2]f(i,v) = 0 (i<=1, vf(i,v) = c[0] (i==1, v>=p[0]);f(i,v) = f(i-1,v) (i>1, vf(i,v) = max(f(i-1,v), f(i-1,v-w[i-1])+c[i-1])(i>1, v>=w[i-1])我们每次从左⾄右，保存前⼀次的数据从上⾄下时，保存前⼀⾏的数据所以我们总的来说只⽤保存⼀⾏的数据，空间复杂度为O(V)时间复杂度为O(N*V),空间复杂度为O(V);但是，如果我们⽤原始的递归办法去做，即排列组合的⽅法去做时时间复杂度为O(2^N);那么当V很⼤，N较⼩时，⽐如V=1000，N=6时，⽤递归只⽤计算2^6=64次，⽽备受推崇的动态规划就需要计算1000*6=6000次所以说，算法没有绝对的好坏，关键要看应⽤的惨景
发布评论