您的当前位置:首页正文

JS基于贪心算法解决背包问题

2023-11-30 来源:博科教育

前面我们分享了关于js使用贪心算法解决找零问题,本文我们接着为大家介绍JS基于贪心算法解决背包问题。

贪心算法:在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。寻找最优解的过程,目的是得到当前最优解。

部分背包问题:固定容积的背包能放入物品的总最大价值

物品 A B C D 价格 50 220 60 60 尺寸 5 20 10 12 比率 10 11 6 5

按比例降序尽可能多放入物品

function greedy(values, weights, capacity){ var returnValue = 0 var remainCapacity = capacity var sortArray = [] values.map((cur, index) =>{ sortArray.push({ 'value': values[index], 'weight': weights[index], 'ratio': values[index]/weights[index] }) }) sortArray.sort(function(a, b){ return b.ratio > a.ratio }) console.log(sortArray) sortArray.map((cur,index) => { var num = parseInt(remainCapacity/cur.weight) console.log(num) remainCapacity -= num*cur.weight returnValue += num*cur.value }) return returnValue}var items = ['A','B','C','D']var values = [50,220,60,60]var weights = [5,20,10,12]var capacity = 32 //背包容积greedy(values, weights, capacity) // 320

小编还为您整理了以下内容,可能对您也有帮助:

背包问题贪心算法时间复杂度

背包问题贪心算法时间复杂度如下:

背包问题是一类典型的动态规划问题,贪心算法可以解决其中的某些特殊情况。下面我将简要讨论贪心算法在背包问题上的应用和其时间复杂度。

在背包问题中,我们有一组物品,每个物品有特定的重量和价值。我们的目标是在不超过背包的最大重量的情况下,选择一组物品,使得它们的总价值最大。

贪心算法的基本思想是总是选择当前看来价值最大的物品。在背包问题中,我们首先按照物品的单位重量价值(即价值/重量)从大到小排序,然后从价值最高的物品开始,尽可能多地放入背包,直到背包满为止。

贪心算法的时间复杂度主要取决于排序的复杂性。为了对物品按照单位重量价值进行排序,我们可以使用任何内部排序算法(例如快速排序、归并排序等),其时间复杂度通常是O(n log n),其中n是物品的数量。在对物品排序后,我们需要遍历所有物品并选择放入背包的物品,这需要O(n)的时间复杂度。因此,贪心算法的总时间复杂度是O(n log n)。

需要注意的是,贪心算法不一定能得到最优解。例如,如果物品的重量不是整数,贪心算法可能会得到一个次优解。在这种情况下,我们需要使用动态规划或其他更复杂的方法来得到最优解。

贪心算法 部分背包问题

[背包问题]有一个背包,背包容量是M=150。有7个物品,物品可以分割成任意大小。

要求尽可能让装入背包中的物品总价值最大,但不能超过总容量。

物品 A B C D E F G

重量 35 30 60 50 40 10 25

价值 10 40 30 50 35 40 30

分析:

目标函数: ∑pi最大

约束条件是装入的物品总重量不超过背包容量:∑wi<=M( M=150)

(1)根据贪心的策略,每次挑选价值最大的物品装入背包,得到的结果是否最优?

(2)每次挑选所占重量最小的物品装入是否能得到最优解?

(3)每次选取单位重量价值最大的物品,成为解本题的策略。 ?

值得注意的是,贪心算法并不是完全不可以使用,贪心策略一旦经过证明成立后,它就是一种高效的算法。

贪心算法还是很常见的算法之一,这是由于它简单易行,构造贪心策略不是很困难。

可惜的是,它需要证明后才能真正运用到题目的算法中。

一般来说,贪心算法的证明围绕着:整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。

对于例题中的3种贪心策略,都是无法成立(无法被证明)的,解释如下:

(1)贪心策略:选取价值最大者。反例:

W=30

物品:A B C

重量:28 12 12

价值:30 20 20

根据策略,首先选取物品A,接下来就无法再选取了,可是,选取B、C则更好。

(2)贪心策略:选取重量最小。它的反例与第一种策略的反例差不多。

(3)贪心策略:选取单位重量价值最大的物品。反例:

W=30

物品:A B C

重量:28 20 10

价值:28 20 10

根据策略,三种物品单位重量价值一样,程序无法依据现有策略作出判断,如果选择A,则答案错误。

背包问题——贪心算法

•贪心算法的特点是每个阶段所作的选择都是局部最优的,它期望通过所作的局部最优选择产生出一个全局最优解。

贪心与动态规划: 与动态规划不同的是,贪心是 鼠目寸光 ;动态规划是 统揽全局 。

–动态规划:每个阶段产生的都是全局最优解

•第i阶段的“全局”: 问题空间为(a1, … , ai)

•第i阶段的“全局最优解”:问题空间为 (a1, … , ai)时的最优解

–贪心:每个阶段产生的都是局部最优解

•第i阶段的“局部”:问题空间为按照贪心策略中的优先级排好序的第i个输入ai

•第i阶段的“局部最优解”: ai

•贪心选择性质:所求问题的全局最优解可以通过一系列局部最优的选择(即贪心选择)来达到。

–这是贪心算法与动态规划算法的主要区别。

•最优子结构性质:当原问题的最优解包含子问题的最优解时,称此问题具有最优子结构性质。

最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征

背包问题的贪心算法时间复杂度

背包问题的贪心算法时间复杂度论述如下:

1、背包问题是一个经典的组合优化问题,目标是选择一组物品放入限定容量的背包中,使得物品的总价值最大化。贪心算法是一种常用的解决背包问题的方法之一,它通过在每一步选择当前情况下的最优解来逐步构建整体的解。

2、贪心算法的时间复杂度取决于算法的具体实现方式和问题规模。下面我将讨论两种常见的背包问题及其贪心算法的时间复杂度。

3、0-1背包问题:0-1背包问题是最基本的背包问题,假设背包容量为C,有n个物品,每个物品有重量w和价值v。问题要求从这n个物品中选择一部分物品放入背包中,使得放入背包的物品总价值最大,同时总重量不超过背包的容量。

4、贪心算法的基本思想是按照物品的单位价值(即价值除以重量)进行排序,然后依次将单位价值最高的物品放入背包中,直到背包放满或者没有物品可选。

5、时间复杂度分析:在一般情况下,贪心算法的时间复杂度为O(nlogn),其中n为物品的数量。这是因为算法需要对n个物品进行排序,排序的时间复杂度为O(nlogn)。之后,从头到尾依次选择物品放入背包需要O(n)的时间。因此,总的时间复杂度为O(nlogn)。

6、分数背包问题:分数背包问题是背包问题的变种,与0-1背包问题不同的是,分数背包问题中物品可以被分割成任意大小,而不是只能选择整个物品或者不选择。

7、贪心算法的基本思想是按照物品的单位价值进行排序,然后依次选择单位价值最高的物品,直到背包放满或者没有物品可选。如果某个物品无法完整装入背包中,那么可以将它分割成若干部分,选择其中一部分放入背包中,以便达到最优解。

8、时间复杂度分析:在分数背包问题中,贪心算法的时间复杂度也为O(nlogn),其中n为物品的数量。排序的时间复杂度为O(nlogn),将物品划分成若干部分需要O(n)的时间。因此,总的时间复杂度为O(nlogn)。

博科教育还为您提供以下相关内容希望对您有帮助:

用贪心算法设计0-1背包问题。要求:说明所使用的算法策略;写出算法实现...

【答案】: 首先计算每种物品单位重量的价值Vi/Wi,然后,依贪心选择策略,将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后,背包内的物品总重量未超过C,则选择单位重量价值次高的物品并尽可能多...

背包问题贪心算法时间复杂度

贪心算法的基本思想是总是选择当前看来价值最大的物品。在背包问题中,我们首先按照物品的单位重量价值(即价值/重量)从大到小排序,然后从价值最高的物品开始,尽可能多地放入背包,直到背包满为止。贪心算法的时间复杂度主...

背包问题——贪心算法

•第i阶段的“局部”:问题空间为按照贪心策略中的优先级排好序的第i个输入ai •第i阶段的“局部最优解”: ai •贪心选择性质:所求问题的全局最优解可以通过一系列局部最优的选择(即贪心选择)来...

为什么贪心算法不能解0-1背包问题

贪心算法解决背包问题有几种策略:(i)一种贪婪准则为:从剩余的物品中,选出可以装入背包的价值最大的物品,利用这种规则,价值最大的物品首先被装入(假设有足够容量),然后是下一个价值最大的物品,如此继续下去。这种策...

用贪心算法求解背包问题的最优解。

你这个是部分背包么?也就是说物品可以随意分割?那么可以先算出单位重量物品的价值,然后只要从高价值到低价值放入就行了,按p[i]/w[i]降序排序,然后一件一件加,加满为止!贪心的思路是:加最少的重量得到更大的价值...

贪心算法 部分背包问题

(1)背包问题最优值的结构 动态规划的逆向思维法的第一步是刻画一个最优值的结构,如果我们能分析出一个问题的最优值包含其子问题的最优值,问题的这种性质称为最优子结构。一个问题的最优子结构性质是该问题可以使用...

贪心算法解决特殊0-1背包问题

void 0_1_Knapsack(float w[], int n, float c,int x[]) //w[]为每个物品的重量,c为背包容量 { int i;for(i=1;i&lt;=n;i++) x[i]=0;for(i=1;i&lt;=n;i++){ if(w[i]&gt;c) break;x[i]=...

贪心算法的例题分析

一般来说,贪心算法的证明围绕着:整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。对于例题中的3种贪心策略,都是无法成立(无法被证明)的,解释如下:⑴贪心策略:选取价值最大者。反例:W=30物品:A ...

贪婪算法几个经典例子

问题一:贪心算法的例题分析 例题1、[0-1背包问题]有一个背包,背包容量是M=150。有7个物品,物品不可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大,但不能超过总容量。物品 A B C D E F G重量 35kg 30kg 6kg 50...

求背包问题贪心算法实例结果

找零钱问题:以人民币1元,2元,5元,10元,20元,50元,100元为例,要求所找的张数最少 背包问题:假设物体重量W1,W2...Wn其对应的价值为P1,P2...Pn,物体可分割,求装入重量限制为m的背包中的物体价值最...

Top