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