#include <iostream>
using namespace std;

int dp[100001];
int max(int* a, int len, int n)
{
	int tmp = 0;
	for (int i=1; i<=len; i++)
	{
		if (tmp<a[i]) 
		{
			tmp = a[i];
			n = i;
		}
	}
	return tmp;
}

int main()
{
	int cash, N;
	while(scanf("%d%d",&cash,&N) != EOF)
	{
		//输入并初始化数据
		int* n = new int[N+1];
		int* D = new int[N+1];
		memset(dp, 0, sizeof(dp));
		memset(n, 0, (N+1)*sizeof(int));
		memset(D, 0, (N+1)*sizeof(int));
		for (int i=1; i<=N; i++)
			scanf("%d%d", n+i, D+i);

		//DP流程
		for (int i=0; i<=cash; i++)
		{
			int* tmp = new int[N+1];
			memset(tmp, 0, (N+1)*sizeof(int));

			//DP公式
			for (int j=1; j<=N; j++)
			{
				if ((n[j] > 0)&&(i >= D[j]))
					tmp[j] = dp[i-D[j]] + D[j];
			}
			int m=0;
			dp[i] = max(tmp, N, m);
			n[m]--;
			delete tmp;
		}
		printf("%d\n", dp[cash]);
		delete D;
		delete n;
	}

	return 0;
}

• Re:求帮助！！WA！！结果都是正确的 (80) Agencymlf 2013-11-29 10:28:06