ToB企服应用市场:ToB评测及商务社交产业平台

标题: 金矿题目 [打印本页]

作者: 杀鸡焉用牛刀 时间: 2025-1-12 22:08
标题: 金矿题目
10.金矿题目

题目

有5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人人数也不同。例如有的金矿储量是500kg黄金，需要5个工人来挖掘，有的金矿储量是200kg黄金，需要3个工人来挖掘......
如果参与挖矿的工人的总数是10。每座金矿要么全挖，要么不挖，不能派出一半人挖取一半的金矿。要求计算出，最大挖取的黄金值。

int[] g = {400, 500, 200, 300, 350};//金矿储量
int[] p = {5, 5, 3, 4, 3};//挖取需要的工人数量

复制代码

思路

如果使用贪心算法，局部情况最优解，但是团体上却未必最优。好比，计算每个金矿的人均产值，为{80,100,66.6,75,116.6}，单位是kg/人，每一步最优的话，就是挖取350/3人的金矿，和500/5人的金矿，然后就无法挖取了，这里挖取的金矿是850kg，但是还有比这个高的，400/5，500/5人的挖取就是900kg。
这里提供正确思路，其实这个题目，是典型的动态规划题目。动态规划就是把复杂的题目简化为规模较小的子题目，再从简朴的子题目自底向上的一步一步递推，最终得到复杂题目的最优解。
对于金矿，只有挖和不挖，两种选择。假设350kg/3人的，金矿不挖，题目就会转成10人挖前4个金矿的最优解，但是这个只是假设的最优，是否最优，还需要和挖350kg/3人的金矿，然后加上7个人挖前4个的金矿的最优解。比力那个大，那个就是最优解。这两种情况，就是全局题目的最优子结构。
就这样，对于每个金矿，都有挖和不挖，题目就一分为二，二分为四，一直把题目简化到0个金矿或0个工人时的最优选择，这个收益效果显然是0，也就是题目的边界。
这些就是动态规划的要点，确定题目的，全局最优解，和最优子结构之间的关系，以及题目的边界。这个关系用数学公式表达的话，就是状态转移方程式。
金矿数目为n，工人数目为w，金矿的含金量设为数组g[]，金矿所需开采人数为p[]。设f(n,w)为n个金矿，w个工人时的最优收益函数，则该题目的状态转移方程式为，特别重要，后续2，3版本的代码，都要理解这个状态转移函数。

f(n,w) = 0(n=0 或 w=0) //问题的边界
f(n,w) = f(n-1,w) (n>=1,w<p[n-1]) //工人数量，不够挖取当前金矿
f(n,w) = max(f(n-1,w),f(n-1,w-p[n-1]) + g[n-1]) (n >=1,w>=p[n-1]) //工人数量，可以挖取当前金矿

复制代码

代码

[code]//递归 /** * 获取金矿最佳收益 * * @param n 当前金矿数目 * @param w 当前工人人数 * @param g 金矿含量数组 * @param p 对应金矿含量所需人数数组 * @return 返回当前工人人数，和金矿数目的最佳收益函数 * 递归方式计算，的时间复杂度为O(2^n)，适合于金矿数目小时的情况 * 注意这个n是当前金矿的数目，就好比每一个金矿都要分成2种情况，每个金矿下的其他金矿又有两种情况，组合起来看是一个满二叉树， * 节点的个数和层级有关也就是金矿的数目有关为2^n(n为层级，这个题目中为金矿的个数) */ public static int getBestGoldMining(int n, int w, int[] g, int[] p) { if (n

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)