[动态规划] 二、国王和金矿

题目

有一个国家发现了5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人数也不同。参与挖矿工人的总数是10人。
每座金矿要么全挖，要么不挖，不能派出一半人挖取一半金矿。要求用程序求解出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？
工人：10名
金矿：400金/5人、500金/5人、200金/3人、300金/4人、350金/3人、

动态规划问题建模阶段

设金矿数量为 N, 工人数量为 W, 金矿黄金量为 G[], 金矿用工量为 P[]

工人数      | 0  1  2   3   4    5    6    7    8    9    10
——————————-+———————————————————————————————————————————————
第一座金矿  | 0  0  0   0    0   400  400  400  400  400  400
第二座金矿  | 0  0  0   0    0   500  500  500  500  500  900
第三座金矿  | 0  0  0  200  200  500  500  500  700  700  900
第四座金矿  | 0  0  0  200  300  500  500  500  700  800  900
第五座金矿  | 0  0  0  350  350  500  550  650  850  850  900

规律：
    3金矿8工人  = max( 2金矿8工人, 2金矿5工人+第三座金矿)  = max(500, 500+200)
    5金矿10工人 = max( 4金矿10工人, 4金矿7工人+第五座金矿) = max(900, 500+350)
    ……
    由此可见，只需要存储前一行的结果，就可以推导出新的一行。

动态规划三个重要的概念

最优子结构：
由于第五座金矿可挖可不挖，所以10人5座金矿的最优子结构有两种（选最大值）:
10人4座金矿的挖金总量 和 前四座金矿的挖金总量+第五座金矿的挖金总量
= Max( F(4,10), F( 4,10-P[4] ) + G[4] )
边界：
只有一座金矿时，如果工人够，那就是金矿的黄金量；如果工人不够，挖金总量就是0
当 N = 1, W >= P[0]时, F(N,W) = G[0];
当 N = 1, W < P[0]时, F(N,W) = 0
状态转移公式：

1. F(N, W) = 0, ( N <= 1, W < P[0] )小于等于一座金矿，工人人数不够开挖
2. F(N, W) = G[0], ( N == 1, W >= P[0] ) 只有一座，工人人数够开挖
3. F(N, W) = F(N - 1, W), ( N > 1, W < P[N - 1] ) 最后一座金矿不挖
4. F(N, W) = max( F(N - 1, W), F(N - 1, W - P[N - 1]) + G[N - 1] ) ,( N > 1, W >= P[N - 1] ) 取最后一座金矿挖与不挖的最大值

动态规划求解问题阶段

class Index
{
    /**
     * 动态规划（Dynamic Programming）
     * 时间复杂度：O(N * W)
     * 空间复杂度：O(W)
     */
    public function test()
    {
        $N   = 5;                                // 金矿数量
        $W   = 10;                               // 工人数量
        $P   = array(5, 5, 3, 4, 3);             // 每座金矿需要的用工数
        $G   = array(400, 500, 200, 300, 350);   // 每座金矿的金矿重量
        $pre = $res = [];                        // 存储前一行结果、最终结果

        // 只有一座金矿时的情况：如果当前循环工人数($i)小于第一座金矿所需工人数(P[0])，则为 0，否则就是第一座金矿的重量
        for ($i = 0; $i <= $W; $i++) {
            $pre[$i] = ($i < $P[0]) ? 0 : $G[0];
        }

        for ($i = 1; $i < $N; $i++) {       // 循环金矿，从第二座金矿开始
            for ($j = 0; $j <= $W; $j++) {  // 循环工人数
                // 如果工人数不够挖最后一座金矿，则等于上一层的结果；如果工人数够挖最后一座，则取最大值
                $res[$j] = ($j < $P[$i]) ? $pre[$j] : max($pre[$j], $pre[$j - $P[$i]] + $G[$i]);
            }
            $pre = $res;
        }
        print_r($res[$W]);  // 900
    }
}

参考：程序员小灰

本作品采用《CC 协议》，转载必须注明作者和本文链接