开心的金明 （C++代码）

解题思路： 状态转移方程：

注意事项:    背包问题

参考代码:

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

int main(){
	int dp[26][3000];
	int val[26],w[26];
	int d,money,i,j;
	cin>>money>>d;
	for(i=1;i<=d;i++)
		cin>>val[i]>>w[i];
	memset(dp,0,sizeof(dp));    //初始化 
		for(i=0;i<=d;i++){
			for(j=0;j<=money;j++){
				if(j<val[i])    dp[i][j]=dp[i-1][j];
				else 	dp[i][j]=max(dp[i-1][j],dp[i-1][j-val[i]]+val[i]*w[i]);
			}
		}
	cout<<dp[d][money];
	return 0;
}