学步园

题目链接：http://poj.org/problem?id=2063

题意：给定本金、年限、债券和相应的利息，问买怎样的债券能够获得最多的利息，输出年限后的本息。

思路：完全背包。注意： The value of a bond is always a multiple of $1 000.利用这点可大大降低复杂度。

#include <cstdio>
#include <cstring>
#define max(x,y) ((x)>(y)?(x):(y))

int f[50010],bond[15],interest[15];
int sum,year,n;

int CompletePack ()
{	
	while (year--)
	{
		memset(f,0,sizeof(f));
		int s=sum/1000;
		for (int i=1;i<=n;i++)
			for (int j=bond[i];j<=s;j++)
				f[j] = max(f[j],f[j-bond[i]]+interest[i]);
		sum+=f[s];
	}
	return sum;
}

int main ()
{
	int T;
	scanf("%d",&T);
	while (T--)
	{
		scanf("%d%d%d",&sum,&year,&n);
		for (int i=1;i<=n;i++)
		{
			scanf("%d%d",&bond[i],&interest[i]);
			bond[i]/=1000;
		}
		printf("%d\n",CompletePack ());
	}
	return 0;
}