国王与金矿

有一个国家发现了5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人数也不同。参与挖矿工人的总数是10人。每座金矿要么全挖，要么不挖，不能派出一半人挖取一半金矿。要求用程序求解出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？(其实就是经典的背包问题，当然这个问题是来微信公众号-程序员小灰的，当然内容都是有自己思考的，他的文章中代码部分有部分错误)

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

最简单的思路还是暴力，先找出可以挖的矿的最值，显然是2 ~ 3，也就是说从可以五个矿里面选择2 ~ 3个矿开始挖，排列组合一下，再剔除人力要求超过10的，取挖金数最多的就好

  1. int maxGold(const std::vector<int> &gold, const std::vector<int> &manNumNeed, int manNum)
  2. {
  3. //增加空间开销
  4. std::vector<int> m = manNumNeed;
  5. //需要排序算法，有一定时间复杂度O(nlogn)
  6. sort(manNumNeed);
  7. int i = 0;
  8. int min = 0;
  9. int max = 0;
  10. int sum = 0;
  11. while (sum <= manNum && i < m.size())
  12. {
  13.     sum += m[i];
  14.     ++i;
  15.     ++max;
  16. }
  17. i = m.size();
  18. while (sum <= manNum && i >= 0)
  19. {
  20.     sum += m[i];
  21.     --i;
  22.     ++min;
  23. }
  24. for (int j = min; j <= max; ++j)
  25. {
  26.     // 这里进行排列组合并求人数需求，显然又是一个指数级算法
  27. }
  28. }

显然暴力枚举是不行的，那么我们用动态规划思想想一想：四座金矿与五座金矿的问题有什么关联呢。显然第五座金矿存在挖和不挖的情况，如果不挖，那么就是四座金矿的问题，如果挖，那就是四座金矿7个人的问题。

我们用gold[N-1],manN-1分别表示开采第N座矿所得到的金与所需要的人,用F(N,M)表示N座金矿M个人的问题，那么

  1. F(N, M) = MAX(F(N - 1, M), F(N - 1, M - man[N - 1]) + gold[N - 1])
  2. F(5, 10) = MAX(F(4, 10), F(4, 10 - 3) + 350)
  3. F(4, 10) = MAX(F(3, 10), F(3, 7 - 4) + 300)
  5. if (M > man[1])
  6. {
  7.     F(1, M) = gold[0];
  8. }
  9. else
  10. {
  11.     F(1, M) = 0;
  12. }

不妨先把递归算法先写出来

  1. #define D_N 100
  3. int man[D_N];
  4. int gold[D_N];
  6. int F(int N, int M)
  7. {
  8. if (N == 1)
  9. {
  10.     if (M > man[0])
  11.     {
  12.         return gold[0];
  13.     }
  14.     else
  15.     {
  16.         return 0;
  17.     }
  18. }
  19. else
  20. {
  21.     int a = F(N - 1, M);
  22.     int b = F(N - 1, M - man[N - 1])+gold[N-1];
  23.     return (a > b) ? a : b;
  24. }
  25. }

其结构类似于二叉树，时间复杂为O(2^n),空间复杂度为O(n)

如何将其转换成非递归呢，因为我们无法确定底层每个F(1,i )的i具体有哪些，因为确定过程涉及到排列组合，没必要将问题复杂化，所以我们将F(F1,i)的所有数据都存下来，那么必定能得出F(2,i)的所有值，依此类推，求出我们需要的F(N, M)；

当然如果对preResult数组理解不了，那么创建一个二维数组F[N][M+1]，从F[1][i]逐步填充，，便不需要移动，也便于理解。算法实现如下：

  1. int maxgoldold(const std::vector<int> &gold, const std::vector<int> &man, int N, int M)
  2. {
  3. int Fn_m = 0;
  4. std::vector<int> preResult(M+1, 0);
  5. std::vector<int> result(M+1);
  6. // 先填充栈底数据
  7. // preResult[j]相当于F(1,j)
  8. // 也就是说这里的j相当于工人数量，这里已经考虑工人数量为0的可能
  9. for (int j = 1; j < M; ++j)
  10. {
  11.     if (j  >= man[0])
  12.     {
  13.         preResult[j] = gold[0];
  14.     }
  15. }
  16. // i是金矿数量，j是工人数量
  17. // man与gold显然都是与第i+1个金矿相关的
  18. // 因为第一个金矿已经分析存值了，所以从第二个开始
  19. for (int i = 1; i < N; ++i)
  20. {
  21.     //工人不需要从0个开始判断
  22.     for (int j = 1; j <= M; ++j)
  23.     {
  24.         // 如果工人比当前矿所需人还少，那当前矿显然只能放弃，也就是max中选左边的
  25.         if (j  < man[i])
  26.         {
  27.             result[j] = preResult[j];
  28.         }
  29.         else
  30.         {
  31.         // 考虑 j-man[i]==0 所以前面result数组长度为M+1
  32.         result[j] = max(preResult[j], preResult[j  - man[i]] + gold[i]);
  33.         }
  34.     }
  35.     preResult = result;
  36. }
  37. return result[M];
  38. }

点击关注，持续推送质量好文；如有不当，欢迎指出；转载请注明出处。