动态规划问题----国王和金矿

2018-02-18 19:48:53来源:cnblogs.com作者:fengranqingwu人点击

分享
问题:有一个国家发现了5座金矿,每座金矿的黄金储量不同,需要参与挖掘的工人数也不同。参与挖矿工人的总数是10人。每座金矿要么全挖,要么不挖,不能派出一半人挖取一半金矿。要求用程序求解出,要想得到尽可能多的黄金,应该选择挖取哪几座金矿?
动态规划有三个核心元素:最优子结构、边界、状态转移 方程式。该问题中要求10个工人5个金矿,挖最多黄金的选择。因此最优子结构有两种情况:
  1. 10个工人4个金矿时,挖出最多黄金的选择。
  2. 4金矿,工人数:10-最后一个金矿需要的人数。
我们把金矿数量设为n,工人数设为m,金矿的黄金量设为g[],金矿的用工量设为数组p[],该问题中,各数据如下所示:n=5,    m=10,    g = [400,500,200,300,350],    p = [5,5,3,4,3]那么5座金矿和4做金矿的最优选择之间存在这样的关系:F(5,10) = MAX(F(4,10),F(4,10-P[4]+G[4]))现在给出边界,也就是金矿数量n为1时:当n=1,m>=p[0]时,F(n,m) = g[0];当n=1,m<p[0]时,F(n,m) = 0;使用格子推导出所有的情况:   对某一情况进行分析,如F(3,8),其结果就是MAX(F(2,8),F(2,8-P[3]) + G[3]) = 700 状态转移方程:F(n,m) = 0 (n<=1,m<p[0]);F(n,m) = g[0](n==1,m>=p[0]);F(n,m) = F(n-1,m)(n>1,m<p[n-1]);F(n,m) = max(F(n-1,m), F(n-1,m-p[n-1])+g[n-1])(n>1,m>=p[n-1]); js代码如下://n:金矿数量       m:工人数量      g:获得金额数组       p:需要工人数组                  function getMostGold(n,m,g,p){                        var preResults = [];                        var results = [];                        for(var i = 0; i <= m; i++){                              if(i < p[0]){                                    preResults[i] = 0;                              }else{                                    preResults[i] = g[0];                              }                        }                        for(var t = 0;t < preResults.length; t++){                              results[t] = preResults[t];                        }                                   if(n == 1){                              return results[m];                        }                        for(var i = 1;i < n; i++){                              for(var j = 0; j <= m; j++){                                    if(j < p[i]){                                          results[j] = preResults[j];                                    }else{                                          //实际上就是管不管最后一个金矿的问题                                          results[j] = Math.max(preResults[j],preResults[j-p[i]] + g[i]);                                                                            }                              }                              console.log(results);                              for(var t = 0;t < preResults.length; t++){                                    preResults[t] = results[t];                              }                        }                        return results[m];                               }                  var g = [400,500,200,300,350];                  var p = [5,5,3,4,3];                  console.log(getMostGold(5,10,g,p)); 其中需要注意的是,js中数组拷贝需要使用深拷贝,使用浅拷贝(preResults = results)会产生数据问题。原文链接如下:http://www.sohu.com/a/153858619_466939                                                 

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台