• 贪心算法--JavaScript实现

            贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅是在某种意义上的局部最优解。

            贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。

             所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。

    一、基本思路：

            1、建立数学模型来描述问题。

            2、把求解的问题分成若干个子问题。

            3、对每一子问题求解，得到子问题的局部最优解。

            4、把子问题的解局部最优解合成原来解问题的一个解。

    二、贪心选择性质： 

           指所求问题的整体最优解可以通过一系列局部最优的选择，换句话说，当考虑做何种选择的时候，我们只考虑对当前问题最佳的选择而不考虑子问题的结果。这是贪心算法可行的第一个基本要素。贪心算法以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。

    三、一般流程

    1. Greedy(C)  //C是问题的输入集合即候选集合
    2. {
    3.     S={ };  //初始解集合为空集
    4.     while (not solution(S))  //集合S没有构成问题的一个解
    5.     {
    6.        x=select(C);    //在候选集合C中做贪心选择
    7.        if feasible(S, x)  //判断集合S中加入x后的解是否可行
    8.           S=S+{x};
    9.           C=C-{x};
    10.     }
    11.    return S;
    12. }

    四、例题分析

          [找零钱问题]美国面额硬币有：1，5，10，25；我们给36美分的零钱，看能得怎样的结果？

    1. function MinCoinChange(coins) {
    2.     var coins = coins;
    3.     var cache = {};
    4.     this.makeChange = function (amount) {
    5.         var change = [], total = 0;
    6.         for (var i = coins.length; i >= 0; i--) {
    7.             var coin = coins[i];
    8.             while (total + coin <= amount) {
    9.                 change.push(coin);
    10.                 total += coin;
    11.             }
    12.         }
    13.         return change;
    14.     }
    15. }
    16. var minCoinChange = new MinCoinChange([1, 5, 10, 25]);
    17. var change = minCoinChange.makeChange(36);
    18. console.log(change)

    [背包问题]

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

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

       用贪心算法解背包问题的基本步骤：首先计算每种物品单位重量的价值v[i]/w[i]，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。

    1. function backpage(){
    2.     var Weight = [35,30,60,50,40,10,25];
    3.     var Value  = [10,40,30,50,35,40,30];
    4.    
    5.     var array = new Array();
    6.     for(var i=0; i<7; i++) //将每件物品重量、价值封装到对象中,放入数组
    7.     {
    8.         var obj = {
    9.             value : Value[i],
    10.             weight : Weight[i],
    11.             char_mark : String.fromCharCode(65+i), //物品名称
    12.             mark : false,
    13.             ratio : (Value[i] / Weight[i]).toFixed(2)//物品的价值比
    14.         }
    15.         array.push(obj);
    16.     }
    17.     
    18.     var str = ""
    19.     for(var i=0;i<7;i++)
    20.         str += array[i].ratio+"\t";
    21.     console.log("价值比：",str);
    22.     
    23.     var weight_all = 0.0; //总重量
    24.     var value_all = 0.0; //总价值
    25.     var max = 0.0;
    26.     var charArray = []; //放入物品的顺序表
    27.     var flag,n = 0;
    28.     var w = ""; //拼接物品重量
    29.     while(weight_all <= 150)
    30.     {
    31.         var max = array[0].ratio
    32.         for(var index=1;index < 7; index++)
    33.         {
    34.             if(array[index].ratio > max && array[index].mark === false)
    35.             {
    36.                 max = array[index].ratio ;
    37.                 flag = index;
    38.             }
    39.         }
    40.         
    41.         charArray[n++] = array[flag].char_mark;
    42.         array[flag].mark = true;
    43.         weight_all += array[flag].weight;
    44.         w += array[flag].weight+ "\t"; 
    45.         value_all += array[flag].value;
    46.         max = 0.0;
    47.     }
    48.     
    49.     str = ""
    50.     for(var j=0;j<n-1;j++)
    51.         str += charArray[j] + "\t";
    52.     console.log("物品顺序：",str);
    53.     console.log("物品重量：",w);
    54.     console.log("weight_all:",weight_all - array[flag].weight); //总重量减去超出的重量
    55.     console.log("value_all:",value_all);
    56. }
    57.  
    58. backpage()

    [活动安排问题]

    设有n个活动的集合e={1，2，…，n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si< fi。如果选择了活动i，则它在半开时间区间[si，fi]内占用资源。若区间[si，fi]与区间[sj，fj]不相交，则称活动i与活动j是相容的。也就是说，当si≥fi或sj≥fj时，活动i与活动j相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。

    在下面所给出的解活动安排问题的贪心算法gpeedyselector中，各活动的起始时间和结束时间存储于数组s和f{中且按结束时间的非减序：．f1≤f2≤…≤fn排列。如果所给出的活动未按此序排列，我们可以用o(nlogn)的时间将它重排。

    1. function testArrangeActivity() {
    2.     var start = [1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12];
    3.     var   end = [4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14];
    4.     var results = arrangeActivity(start, end);
    5.     for (var i = 0; i < results.length; i++) {
    6.         var index = results[i];
    7.         console.log("开始时间:" + start[index] + ",结束时间:" + end[index]);
    8.     }
    9. }
    10. /**
    11.  * 活动安排
    12.  * @param s 开始时间
    13.  * @param e 结束时间
    14.  * @return
    15.  */
    16.  function arrangeActivity(s, e) {
    17.     var total = s.length;
    18.     var endFlag = e[0];
    19.     var results = [];
    20.     results.push(0);
    21.     for (var i = 0; i < total; i++) {
    22.         if (s[i] > endFlag) {
    23.             results.push(i);
    24.             endFlag = e[i];
    25.         }
    26.     }
    27.     return results;
    28. }
    29.  
    30. testArrangeActivity()

    ［均分纸牌］

    有N堆纸牌，编号分别为1，2，…，n。每堆上有若干张,但纸牌总数必为n的倍数.可以在任一堆上取若干张纸牌,然后移动。

    移牌的规则为：在编号为1上取的纸牌，只能移到编号为2的堆上；在编号为n的堆上取的纸牌，只能移到编号为n-1的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如：n=4，4堆纸牌分别为：① 9 ② 8 ③ 17 ④ 6 移动三次可以达到目的：从③取4张牌放到④ 再从③区3张放到②然后从②去1张放到①。

    输入输出样例：4

    9  8  17  6

    屏幕显示：3

    算法分析：设a[i]为第I堆纸牌的张数（0<=I<=n），v为均分后每堆纸牌的张数，s为最小移动次数。

    我们用贪心算法，按照从左到右的顺序移动纸牌。如第I堆的纸牌数不等于平均值，则移动一次（即s加1），分两种情况移动：

    1、若a[i]>v，则将a[i]-v张从第I堆移动到第I+1堆；

    2、若a[i]< v，则将v-a[i]张从第I+1堆移动到第I堆。为了设计的方便，我们把这两种情况统一看作是将a[i]-v从第I堆移动到第I+1堆，移动后有a[i]=v; a[I+1]=a[I+1]+a[i]-v.

    在从第I+1堆取出纸牌补充第I堆的过程中可能会出现第I+1堆的纸牌小于零的情况。

    如n=3，三堆指派数为1  2  27 ，这时v=10，为了使第一堆为10，要从第二堆移9张到第一堆，而第二堆只有2张可以移，这是不是意味着刚才使用贪心法是错误的呢？

    我们继续按规则分析移牌过程，从第二堆移出9张到第一堆后，第一堆有10张，第二堆剩下-7张，在从第三堆移动17张到第二堆，刚好三堆纸牌都是10，最后结果是对的，我们在移动过程中，只是改变了移动的顺序，而移动次数不便，因此此题使用贪心法可行的。

    1. /**
    2.  * 均分纸牌
    3.  * @param cards
    4.  * @param heap
    5.  * @return
    6.  */
    7.  function moveCards(cards, heap) {
    8.     //总牌数
    9.     var sum = 0;
    10.     for (var i = 0; i < cards.length; i++) {
    11.         sum += cards[i];
    12.     }
    13.     //每堆平均牌数
    14.     var avg = sum / heap;
    15.     //移动次数
    16.     var count = 0;
    17.     for (var j = 0; j < cards.length; j++) {
    18.         if(cards[j] != avg) {
    19.             var moveCards = cards[j] - avg;
    20.             cards[j] -= moveCards;
    21.             cards[j + 1] += moveCards;
    22.             count++;
    23.         }
    24.     }
    25.     return count;
    26. }
    27.  
    28. function testMoveCard() {
    29.     //总共4堆
    30.     var heap = 4;
    31.     var  cards = [9, 8, 17, 6];
    32.     var count = moveCards(cards, heap);
    33.     console.log("移动次数:" + count);
    34.     for (var i = 0; i < cards.length; i++) {
    35.         console.log("第" + (i + 1) + "堆牌数:" + cards[i]);
    36.     }
    37. }
    38.  
    39. testMoveCard()

    ［最大整数］

    设有n个正整数，将它们连接成一排，组成一个最大的多位整数。

    例如：n=3时，3个整数13，312，343，连成的最大整数为34331213。

    又如：n=4时，4个整数7，13，4，246，连成的最大整数为7424613。

    输入：n

    N个数

    输出：连成的多位数

    算法分析：先把整数转换成字符串，然后在比较a+b和b+a，如果a+b>=b+a，就把a排在b的前面，反之则把a排在b的后面。

    1. /**
    2.  * 根据给定的整数组成最大的多位数
    3.  * @param nums
    4.  */
    5.  function maxNum(nums) {
    6.     var result = "";
    7.     for (var i = 0; i < nums.length; i++) {
    8.         var num1 = nums[i] + ""; //转换为字符串
    9.         for (var j = 1; j < nums.length; j++) {
    10.             var num2 = nums[j] + "";
    11.             if ((num1 + num2)<(num2 + num1)) {
    12.                 var temp = nums[j];
    13.                 nums[j] = nums[i];
    14.                 nums[i] = temp;
    15.             }
    16.         }
    17.     }
    18.     for (var i = 0; i < nums.length; i++) {
    19.         result += nums[i];
    20.     }
    21.     return result;
    22. }
    23.  
    24. function testMaxNum() {
    25.     //有n个正整数，将它们连接成一排，组成一个最大的多位整数
    26.     //12112错误
    27.     //12121正解
    28.     var nums = [12, 121];
    29.     //var nums = [12, 123];
    30.     var result = maxNum(nums);
    31.     console.log("组成最大整数:" + result);
    32. }
    33.  
    34. testMaxNum()

  • 相关阅读:
    私服下载失败，下载不下来
    mysql如何把 一个数据库中的表数据 复制到 另一个数据库中(两个数据库不在同一个数据库链接下)
    【送书】实现可观测性平台的技术要点是什么？
    怎样能更快速的整理软考高项教材的知识考点？
    SHAP 和 LIME 解释模型
    基于SpringBoot设计模式之结构型设计模式·适配器模式
    云服务器与内网穿透有什么区别？哪个好用？
    程序设计与算法（三）C++面向对象程序设计笔记 第七周 输入输出和模板
    解决du和df命令显示磁盘空间不一致的问题
    何为AVOption？AVClass? 及其关联的若干个Context
  • 原文地址：https://blog.csdn.net/m0_37911706/article/details/125327383