开心的金明 （C语言代码）

解题思路:

注意事项:

参考代码:

#include<iostream>
#include<string.h>
using namespace std;

long int dp[26][30001];
pair<int,int> wuping[26]; 	//first是价格 second 是期望值 
long int  dfs(int i,int amount,int d){
	long int res;
	if(dp[i][amount]!=-1)
	return  dp[i][amount]; 
	if(i == d+1)
		res = 0;
	else if(wuping[i].first > amount)
		 res=dfs(i+1,amount,d);
	else
		 res=max(dfs(i+1,amount,d),dfs(i+1,amount-wuping[i].first,d) + wuping[i].first*wuping[i].second);
	return dp[i][amount]=res;
}

int main(){
	int maxMoney,d;	//d物品个数 ：从1- d 排序
	cin>>maxMoney>>d;
	for(int i=1;i<=d;i++)
		cin>>wuping[i].first>>wuping[i].second;
		memset(dp,-1,sizeof(dp));
	cout<<dfs(1,maxMoney,d);
	return 0;
}