挖金矿

挖金矿

一、问题描述

有 5 座金矿,每座金矿的黄金储量不同,需要参与挖掘的工人数也不同。参与挖矿工人的总数是 10 人。每座金矿要么全挖,要么不挖,不能派出一半人挖取一半金矿。要求用程序求解出,要想得到尽可能多的黄金,应该选择挖取哪几座金矿?

挖金矿

二、算法分析

w 表示总共人数,n 表示金矿数,

  1. 排列组合

    每一座金矿都有挖与不挖两种选择,排列组合起来就有 2n 种选择。对所有可能性做遍历,剔除那些使用工人数超过 10 的选择,在剩下的选择里找出获得金币数最多的选择。

    时间复杂度:O(2n)。

  2. 递归

    每个金矿存在"挖"、"不挖"两种情况,可以同时内部调用两次递归方法,表示"挖"和"不挖"。

    void A()
    {
    if (边界条件) return x;
    // 挖
    A();
    // 不挖
    A();
    }

    时间复杂度:O(2n) 开辟空间:递归深度 O(n)

  3. 动态规划

    这个问题与 0-1 背包问题相同,动态规划时的策略也是:当前金矿是否应该挖,挖与不挖的价值比较。整理出以下表格。

    挖金矿

上一篇:求正2n边形的最小外接正方形


下一篇:【数据结构与算法】第2章-算法