题目：

10 个工人

5个金矿，每个金矿对应收益和所需工人如下

400kg/5人 500kg/5人 200kg/3人 300kg/4人 350kg/3人

每个金矿要么全挖，要么不挖，不能派出一半人挖取一半金矿

求最佳金矿收益

stag1

对于问题中的每个金矿来说，都存在着 “挖”、”不挖” 两个选择，

则对于 10个工人 5个金矿 400kg/5人 500kg/5人 200kg/3人 300kg/4人 350kg/3人求最佳收益可以转化为：

最后一个金矿挖： 7个工人 4个金矿 400kg/5人 500kg/5人 200kg/3人 300kg/4人 + 最后一个挖的金矿 350kg

最后一个金矿不挖：10个工人 4个金矿 400kg/5人 500kg/5人 200kg/3人 300kg/4人

这两种情况的下收益的最大值

同样，对于前 4 个金矿也可以进一步转换

7个工人 4个金矿 400kg/5人 500kg/5人 200kg/3人 300kg/4人可以转换为

最后一个金矿挖： 3个工人 3个金矿 400kg/5人 500kg/5人 200kg/3人 + 最后一个挖的金矿 300kg

最后一个金矿不挖：7个工人 3个金矿 400kg/5人 500kg/5人 200kg/3人

10个工人 4个金矿 400kg/5人 500kg/5人 200kg/3人 300kg/4人可以转换为

最后一个金矿挖：6个工人 3个金矿 400kg/5人 500kg/5人 200kg/3人 + 最后一个挖的金矿 300kg

最后一个金矿不挖：10个工人 3个金矿 400kg/5人 500kg/5人 200kg/3人

同理，上述四种情况还可以进一步拆分，则问题一分为二，二分为四，一直把问题简化到 0 个金矿或者 0 个工人时的最优选择，这个时候收益为 0 ，也是问题的边界

这就是动态规划的要点：确定全局最优解和最优子结构之间的关系，以及问题边界

这种关系用数学公式来表达的话，就叫状态转移方程

设工人数量为 w，金矿数量为 n，金矿含量为数组 g，金矿开采所需的人数为数组 p

F(n, w) 为n个金矿，w个工人时的最优收益函数

则：

问题边界，金矿数为 0 或工人数为 0 时

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])

由状态转移方程得分解图如下

导图连接

根据状态转移方程实现代码如下：

    /**
     * @param {number} w   工人数量
     * @param {number} n  可选金矿的数量
     * @param {Array<number>} p  金矿开采所需的工人数量
     * @param {Array<number>} g  金矿储量
     */
    function getBestColMiningV1(w:number, n:number, p:Array<number>, g:Array<number>):number {
        if(w === 0 || n ===0) {
            return 0
        }
        if(w < p[n-1]) {
            return getBestColMiningV1(w, n-1, p, g)
        }
        return Math.max(
            getBestColMiningV1(w, n-1, p, g),
            getBestColMiningV1(w - p[n-1], n-1, p, g) + g[n-1]
        )
    }

  console.log(getBestColMiningV1(10,5, [5,5,3,4,3], [400, 500, 200, 300, 350]))
复制代码

该算法若在工人充足的情况下时间复杂度为 O(2n)，即每个矿都有两种情况

Stag2

分析上述分解图可以看出

F(2,7)，及其子分支，在相同参数的情况下被计算了两次，目前金矿数量为 5，当金矿数量越来越多，重复调用必然越来越多

如何优化这个问题，就需要引入动态规划的另一个核心要点：自底向上求解

首先创建一个表格，用于记录选择金矿的中间过程

表格的最左侧代表不同的金矿，从上到下，每多增加一行，则代表多一个可选的金矿，也就是F(n,w)中的 n 值

表格的最上方代表工人的数量，从一个工人到十个工人，也就是F(n,w)中的 w 值

空白格子代表给出 n 个工人， w 个金矿时的最佳收益，也就是 F(n, w)的值

下边可以从第一行，第一列开始，尝试把空白格子填满，填充的依据就是状态转移方程：

第一行的前四个格子由于 w < p[n-1]，则对应的状态转移方程如下：

F(n, w) = F(n – 1, w) (n>1, w<p[n-1])

带入求解得：

F(1, 1) = F(1-1, 1) = F(0, 1) = 0

F(1, 2) = F(1-1, 2) = F(0, 2) = 0

F(1, 3) = F(1-1, 3) = F(0, 3) = 0

F(1, 4) = F(1-1, 4) = F(0, 4) = 0

第一行的后六个格子，由于 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])

带入求解得：

F(1, 5) = Max(F(1-1, 5), F(1-1, 5-5) + 400KG) = Max(0, 400KG) = 400KG

F(1, 6) = Max(F(1-1, 6), F(1-1, 6-5) + 400KG) = Max(0, 400KG) = 400KG

F(1, 7) = Max(F(1-1, 7), F(1-1, 7-5) + 400KG) = Max(0, 400KG) = 400KG

F(1, 8) = Max(F(1-1, 8), F(1-1, 8-5) + 400KG) = Max(0, 400KG) = 400KG

F(1, 9) = Max(F(1-1, 9), F(1-1, 9-5) + 400KG) = Max(0, 400KG) = 400KG

F(1, 10) = Max(F(1-1, 10), F(1-1, 10-5) + 400KG) = Max(0, 400KG) = 400KG

第二行前四个和第一行同理，由于 w < p[n-1]，所以状态转移方程为：

F(n, w) = F(n – 1, w) (n>1, w<p[n-1])

带入求解得：

F(2, 1) = F(2-1, 1) = 0

F(2, 2) = F(2-1, 2) = 0

F(2, 3) = F(2-1, 3) = 0

F(2, 4) = F(2-1, 4) = 0

第二行后六个同理第一行，由于 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])

带入求解的：

F(2, 5) = Max(F(2-1, 5), F(2-1, 5-5) + 500KG) = Max(F(1, 5), F(1, 0) + 500KG) = Max(400KG, 500KG) = 500KG

F(2, 6) = Max(F(2-1, 6), F(2-1, 6-5) + 500KG) = Max(F(1, 6), F(1, 1) + 500KG) = Max(400KG, 500KG) = 500KG

F(2, 7) = Max(F(2-1, 7), F(2-1, 7-5) + 500KG) = Max(F(1, 7), F(1, 2) + 500KG) = Max(400KG, 500KG) = 500KG

F(2, 8) = Max(F(2-1, 8), F(2-1, 8-5) + 500KG) = Max(F(1, 8), F(1, 3) + 500KG) = Max(400KG, 500KG) = 500KG

F(2, 9) = Max(F(2-1, 9), F(2-1, 9-5) + 500KG) = Max(F(1, 9), F(1, 4) + 500KG) = Max(400KG, 500KG) = 500KG

F(2, 10) = Max(F(2-1, 10), F(2-1, 10-5) + 500KG) = Max(F(1, 10), F(1, 5) + 500KG) = Max(400KG, 900KG) = 900KG

后续计算过程就不详细展示了，这里计算完成结果如下：

此时最后一行最后一列即所要求得的最佳收益，这就是动态规划自底向上求解的过程，转换为代码如下：

    /**
     * @param {number} w 工人数量
     * @param {Array<number>} p 金矿开采所需的工人数量
     * @param {Array<number>} g 金矿储量
     * @returns {number}
     */
    function getBestColMiningV2(w:number,p:Array<number>, g:Array<number>):number {
        let resultArray = new Array(g.length+1);
        for (let index = 0; index < resultArray.length; index++) {
                resultArray[index] = new Array(w+1).fill(0)
        }
        for (let i = 1; i <= g.length; i++) {
            for (let j = 1; j <= w; j++) {
                if(j < p[i-1]) {
                    resultArray[i][j] = resultArray[i - 1][j]
                } else {
                    resultArray[i][j] = Math.max(
                        resultArray[i - 1][j], 
                        resultArray[i - 1][j-p[i-1]] + g[i-1]
                    )
                }
            }
        }
        return resultArray[g.length][w]
    }
    console.log(getBestColMiningV2(10, [5,5,3,4,3], [400, 500, 200, 300, 350]))
复制代码

stag3

上述自底向上求解的代码时间和空间复杂度都是 O(nw)，这段代码在时间上已经没有可以优化的了，但是在空间上还具有可以优化的地方

上边第二行的求解过程：

F(2, 1) = F(2-1, 1) = 0

F(2, 2) = F(2-1, 2) = 0

F(2, 3) = F(2-1, 3) = 0

F(2, 4) = F(2-1, 4) = 0

F(2, 5) = Max(F(2-1, 5), F(2-1, 5-5) + 500KG) = Max(F(1, 5), F(1, 0) + 500KG) = Max(400KG, 500KG) = 500KG

F(2, 6) = Max(F(2-1, 6), F(2-1, 6-5) + 500KG) = Max(F(1, 6), F(1, 1) + 500KG) = Max(400KG, 500KG) = 500KG

F(2, 7) = Max(F(2-1, 7), F(2-1, 7-5) + 500KG) = Max(F(1, 7), F(1, 2) + 500KG) = Max(400KG, 500KG) = 500KG

F(2, 8) = Max(F(2-1, 8), F(2-1, 8-5) + 500KG) = Max(F(1, 8), F(1, 3) + 500KG) = Max(400KG, 500KG) = 500KG

F(2, 9) = Max(F(2-1, 9), F(2-1, 9-5) + 500KG) = Max(F(1, 9), F(1, 4) + 500KG) = Max(400KG, 500KG) = 500KG

F(2, 10) = Max(F(2-1, 10), F(2-1, 10-5) + 500KG) = Max(F(1, 10), F(1, 5) + 500KG) = Max(400KG, 900KG) = 900KG

可以看到第二行的值都是由第一行的数据推导出来的，

如：F(2, 10) = Max(F(2-1, 10), F(2-1, 10-5) + 500KG) = Max(F(1, 10), F(1, 5) + 500KG) = Max(400KG, 900KG) = 900KG

是由 F(1, 10) 和 F(1, 5) 推导出来的

所以我们并不需要保存整个表格，而是只保存一行数据即可，在计算下一行时，自右向左统计(由上可以看出)，把旧数据一个一个替换掉，代码如下：

    function getBestColMiningV3(w:number,p:Array<number>, g:Array<number>):number {
        let resultArray = new Array(w + 1).fill(0);
        for (let i = 1; i <= g.length; i++) {
            for (let j = w; j >= 1; j--) {
                if(j >= p[i - 1]){
                    resultArray[j] = Math.max(
                        resultArray[j],
                        resultArray[j - p[i -1]] + g[i - 1]
                    )
                }
            }
        }
        return resultArray[w]
    }
    console.log(getBestColMiningV3(10, [5,5,3,4,3], [400, 500, 200, 300, 350]))
复制代码

文章版权归作者所有，未经允许请勿转载。

THE END

前端