动态规划-开心的金明（C++）

解题思路:动态规划

参考代码:

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int n,m;//n:钱 m:物品个数
int dp[30005];
int v[30];//价格 
int p[30]; //重要度 
int main(){
	scanf("%d%d",&n,&m);
	memset(v,0,sizeof(v));
	memset(p,0,sizeof(p));
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=m;i++){
		scanf("%d%d",&v[i],&p[i]);
	}
	for(int i=1;i<=m;i++){
		for(int j=n;j>=v[i];j--){
			dp[j]=max(dp[j],dp[j-v[i]]+p[i]*v[i]);
		}
	}
	printf("%d",dp[n]);
	return 0;
}