Investment 背包

Investment
原题链接https://vjudge.net/contest/348156#problem/A



唔，初始资金为sum 购买 n年的债券，每年都会得到返利，也就是说在n年内，每年都要更新sum 的值，求出每一年购买债券的最大返利。
由于数值较大，所以我们需要将值/1000来计算，这里要注意，我们只改变了我们计算的时候进行比较的背包大小和重量大小这两个比较的关系，sum1，v[i]是记录最大值的数据，并没有改变。

#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;
long long w[100005];
long long v[100005];
long long dp[100005];
int main()
{
	long long sum,n,m,i,j,z,t;
	scanf("%lld",&t);
	while(t--)
	{
		scanf("%lld %lld",&sum,&n);
		scanf("%lld",&m);
		for(i=1; i<=m; i++)
		{
			scanf("%lld %lld",&w[i],&v[i]);
			w[i]=w[i]/1000;//1000的倍数，所以我们可以/1000来计算
		}
		long long sum1=sum;
		for(i=1; i<=n; i++)//n年
		{
			sum=sum1/1000;
			memset(dp,0,sizeof(dp));
			for(j=1; j<=m; j++)
			{
				for(z=w[j]; z<=sum; z++)//完全背包
				{
					dp[z]=max(dp[z],dp[z-w[j]]+v[j]);//求出每一年的最大值
				}
			}
			sum1+=dp[sum];//更新总资产
		}
		printf("%lld\n",sum1);
	}
	return 0;
}