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

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

程序员文章站 2022-06-30 14:51:42
问题: 有一个国家发现了5座金矿,每座金矿的黄金储量不同,需要参与挖掘的工人数也不同。参与挖矿工人的总数是10人。 每座金矿要么全挖,要么不挖,不能派出一半人挖取一半金矿。要求用程序求解出,要想得到尽可能多的黄金,应该选择挖取哪几座金矿? 动态规划有三个核心元素:最优子结构、边界、状态转移 方程式。 ......
问题:
有一个国家发现了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