动态规划简单例子——国王与金矿(c++)

动态规划的要点：确定全局最优解和最优子结构之间的关系，以及问题的边界。以数字的形式表达就是状态转移方程式。下面以一个例子来对他们进行描述。

问题描述：

有一个国家发现了5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人人数也不同。参与挖矿工人的总数是10人。每座金矿要么全挖，要么不挖 ，不能派出一半人挖取一半金矿。要求如何分配工人才能挖出最多的黄金。

第一座金矿含金500，需要5人；第二座金矿含金200，需要3人；第三座金矿含金300，需要4人；第四座金矿含金350，需要3人；第五座金矿含金400，需要5人。

思路：

对于此类提到获得最多的问题，首先想到的一定是做比较，得出在满足人员条件的情况下，选择出含金量最多的方案。

设w为工人总数，n为金矿数，p[]为金矿要的人，g[]为含金量.

将问题细小化，如果只有三座金矿，那么比较方法一定是先看第一座金矿，满足条件则记录数值，此时的员工数减去第一座金矿所需人数，再对第二座金山进行比较，看是否满足人数要求，比较挖和不挖的最大值作为当前的最优结果。以这种思路很容易可以写一个递归的程序，如下：

int getmine(int w,int n,int p[],int g[])
{
if(w==0||n==0) return 0;
if(w

但是这样会导致很多重复计算的值，而且随着数量的增加需要的空间也会越来越大。所以我们可以想到使用一张表来存储结果。由上面的分析可以知道，我们可以将问题简化为一个关于已经挖了4个金矿比较第5个金矿挖与不挖获得含金量多少的比较。

可以直接贴出代码

int getmine_2(int w,int n,int p[],int g[])
{
int a[N][M];
for(int i = 1;i<=n;i++)
a[i][0] = 0;
int i = 1;
for(int j = 1;j<=w;j++)
{
if(j

上图是输出的记录表数值的记录。横向为员工数，纵向为金矿数。

其实在实际求解时，不需要保存这个二维数组，只需要保存最后一行，最后输出数组中最后一个数字即可，这样是为了更好的看出比较的过程。