欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  web前端

JS教程--动态规划算法之背包容量问题

程序员文章站 2022-03-17 14:22:10
...

背包问题

题目
给定 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]

  1. f(i,v) = 0 (i<=1, v<w[0]);

  2. f(i,v) = c[0] (i==1, v>=p[0]);

  3. f(i,v) = f(i-1,v) (i>1, v<w[i-1])

  4. f(i,v) = max(f(i-1,v), f(i-1,v-w[i-1])+c[i-1])(i>1, v>=w[i-1])

JS教程--动态规划算法之背包容量问题

我们每次从左至右,保存前一次的数据
从上至下时,保存前一行的数据
所以我们总的来说只用保存一行的数据,空间复杂度为O(V)
时间复杂度为O(N*V),空间复杂度为O(V);

但是,如果我们用原始的递归办法去做,即排列组合的方法去做时
时间复杂度为O(2^N);

那么当V很大,N较小时,比如V=1000,N=6时,用递归只用计算2^6=64次,而备受推崇的动态规划就需要计算1000*6=6000次

所以说,算法没有绝对的好坏,关键要看应用的惨景

相关推荐:

JS实现动态规划背包算法

JavaScript高级算法之动态规划实例分析

以上就是JS教程--动态规划算法之背包容量问题的详细内容,更多请关注其它相关文章!

相关标签: javascript