首页 > 代码库 > 动态规划 - 金矿模型
动态规划 - 金矿模型
问题描述:
有people个人和num个金矿,开采每个金矿都需要i_People个人,可以获得i_GetGold个金子,并且用过的人不可以重复使用,问从这num个金矿中最多可以得到多少个金子;
输入
输入第一行有两个数,第一个是用来开采金矿的总人数,第二个是总金矿数。
输入文件的第2至n+1行每行有两个数,第i行的两个数分别表示第i-1个金矿需要的人数和可以得到的金子数。
输出
输出一个整数,表示能够得到的最大金子数。
输入样例;
100 5
77 92
22 22
29 87
50 46
99 90
输出样例
133
思路来源:点击这里
下面给出C语言代码:
#include<stdio.h> #include<string.h> #define max_people 10000//程序最多支持的人数 #define max_gold 100//程序最多支持的金矿个数 int Total_People;//可用来挖金矿的总人数 int Total_Gold;//总金矿个数 int i_People[100];//挖第i个金矿所需的人数,程序中第i个金矿用下标i-1表示 int i_GetGold[100];//挖第i个金矿可以得到的金子数目 int max_Gold[max_people][max_gold];//max[i][j]保存了i个人挖前j个金矿(0 -- j-1)能得到的最多金子数目,-1表示未知 //数据初始化 int max(int a,int b) { return a>b?a:b; } void GetData() { scanf("%d%d",&Total_People,&Total_Gold);//读取总人数,和金矿个数 for(int i = 0; i < Total_Gold; i ++) { scanf("%d%d",&i_People[i],&i_GetGold[i]);//读取第i个金矿需要的人数和开采可得到的金子数 } memset(max_Gold,-1,sizeof(max_Gold));//将该数组全部赋值为-1 } //获取people个人开采前num个金矿可以得到的最大金子数 int GetMaxGold(int people,int num)//参数意义:people为可以使用的人数,num为可以开采的金矿个数 { int MaxGold; if(max_Gold[people][num] != -1)//如果这个问题曾经有过记录,即动态规划中的“备忘录” { MaxGold = max_Gold[people][num]; } else if(num == 0)//若可开采的金矿只有一个,即动态规划的“边界条件” { if(people >= i_People[num])//人数满足开采该金矿的所需人数 MaxGold = i_GetGold[num]; else//人数不满足开采该金矿所需的人数 MaxGold = 0; } else if(people >= i_People[num])//若people个人满足开采该金矿,则考虑两种情况(该矿是否开采),取其中的最大值 { MaxGold = max(GetMaxGold(people - i_People[num],num - 1) + i_GetGold[num],GetMaxGold(people,num - 1)); } else //people个人不满足开采该金矿,则只用考虑一种情况(不开采该金矿) MaxGold = GetMaxGold(people,num - 1); max_Gold[people][num] = MaxGold;//记录下当前最多的金子数目,动态规划中的做备忘录 return MaxGold; } int main() { GetData();//读取数据 printf("对多可得到金子为%d\n",GetMaxGold(Total_People,Total_Gold)); return 0; }
动态规划 - 金矿模型
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。