思路：本题和买卖纪念品极为相似，是完全背包问题，总资产相当于背包容量，每种债券的投资额相当于物品体积，利息相当于物品价值。 但由于本题资产数值较大，每种债券的投资额又都是1000的倍数，可以考虑压缩 f 数组， 用 f[j] 表示投资额为 j * 1000时，能够得到的最大利息是多少。

状态转移方程为:

f[j] = max(f[j], f[j - v[i] / 1000] + w[i]);

for (int k = 1; k <= n; k++)
	{
		memset(f, 0, sizeof(f));
		int m = s / 1000;
		for (int i = 1; i <= d; i++)
		{
			for (int j = v[i] / 1000; j <= m; j++)
			{
				if (j >= v[i] / 1000) 
					f[j] = max(f[j], f[j - v[i] / 1000] + w[i]);
			}
		}
		s += f[m];
	}

#include <bits/stdc++.h>
using namespace std;
int s,n,d,v[15],w[15],dp[1000005];
int main(){
    cin >> s >> n >> d;
    for(int i=1;i<=n;i++) cin >> v[i] >> w[i];
    for(int k=1;k<=n;k++){
        memset(dp,0,sizeof(dp));
        int m=s/1000;
        for(int i=1;i<=d;i++)
            for(int j=v[i]/1000;j<=m;j++) 
                dp[j]=max(dp[j],dp[j-v[i]/1000]+w[i]);
        s+=dp[m];
    }
    cout << s;
    return 0;
}

~~ (hetao13775797)

👆

上边这人写的

me 是亿个搬运工😁

#include <bits/stdc++.h> using namespace std; int s,n,d,v[15],w[15],dp[1000005]; int main(){ cin >> s >> n >> d; for(int i=1;i<=n;i++) cin >> v[i] >> w[i]; for(int k=1;k<=n;k++){ memset(dp,0,sizeof(dp)); int m=s/1000; for(int i=1;i<=d;i++) for(int j=v[i]/1000;j<=m;j++) dp[j]=max(dp[j],dp[j-v[i]/1000]+w[i]); s+=dp[m]; } cout << s; return 0; } 本题和买卖纪念品极为相似，是完全背包问题，总资产相当于背包容量，每种债券的投资额相当于物品体积，利息相当于物品价值。 但由于本题资产数值较大，每种债券的投资额又都是1000的倍数，可以考虑压缩 f 数组， 用 f[j] 表示投资额为 j * 1000时，能够得到的最大利息是多少。

状态转移方程为:

f[j] = max(f[j], f[j - v[i] / 1000] + w[i]); 😕 😄 👎 👍 👍

别看这，去讨论 😕