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

2021/12/10 17:17:33

本文主要是介绍动态规划简单例子——国王与金矿(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<p[n-1])//比较当前金矿是否可以挖掘,不能则继续下一座 
	{
		return getmine(w,n-1,p,g);
	}	
	return max(getmine(w,n-1,p,g),getmine(w-p[n-1],n-1,p,g)+g[n-1]);
//在挖与不挖之间作比较,选择最大值 
}

但是这样会导致很多重复计算的值,而且随着数量的增加需要的空间也会越来越大。所以我们可以想到使用一张表来存储结果。由上面的分析可以知道,我们可以将问题简化为一个关于已经挖了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<p[0]) a[i][j] = 0;
		else{
			a[i][j] = g[0];
		}
	} 
	for(int i = 2;i<=n;i++){
		for(int j = 1;j<=w;j++)
		{
			if(j<p[i-1]) {
				a[i][j] = a[i-1][j];
			}
			else{
				a[i][j] = max(a[i-1][j],a[i-1][j-p[i-1]]+g[i-1]);//在比较时,应该看的是人数一定,但不同金矿数而产生不同的收益值 
			}
		}
	
	}
	for(int i = 1;i<=n;i++){
		for(int j = 1;j<=w;j++)
			cout<<a[i][j]<<" ";
		cout<<endl;
	}
} 
image-20211210161419882

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

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

解决时遇到的问题

本题整体思路并不难,只是在人数小于要求时返回0,满足时得到新结果进行一个比较并且记录。

需要注意的是,在比较时应该是a[i-1][j]与a[i-1][j-p[i-1]]+g[i-1],而不是a[i][j-p[i-1]]+g[i-1].只有上层才是对应之前的状态。以及初始化数组时应该给a[i][0]赋初值0。因为如果人数刚好满足j列会需要之前a[i-1][0]的值相加。

思路可能要点乱,看代码就好了,以后技术提高了再修改。



这篇关于动态规划简单例子——国王与金矿(c++)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程