P1853 投资的最大效益 题解

题目传送门

更好的阅读体验

题目大意

有初始总资产 \(s\) 和债券种数 \(d\)，每种债券有投资额和年利息，求 \(n\) 年后的最大总资产。

解题思路

完全背包问题（每种债券可以投资多次）。

把当前总资产看成背包，把债券看成物品。

枚举年数，每次做完全背包，并把最后得到的最大总资产累加，投资到下一年。

完全背包：

• 划分阶段：当前的债券；
• 状态表达：\(f_j\) 表示投资钱数 \(j\) 所获得的最大利息；
• 状态转移：\(f_j=\max(f_j,f_{j-w_i}+v_i)\)；
• 初始状态：\(f_j=0\)；
• 求解目标：\(f_{sum}\)（\(sum\) 为上一年的最大总资产）；

注意求每年的最大总资产时先将 \(f\) 数组清零。

优化：题目中说债券的投资额是 \(1000\) 的倍数，所以可以把债券的投资额都除以 \(1000\)（\(sum\) 也要除以 \(1000\)），最后的结果不变。

代码

AC 记录

#include<bits/stdc++.h>
#define ri register int
using namespace std;
int m,n,d;
int w[15],v[15],f[1000005];
int main() {
	cin>>m>>n>>d;
	int sum=m;//初始总资产
	for(ri i=1; i<=d; i++)cin>>w[i]>>v[i];
	for(ri k=1; k<=n; k++) {
		memset(f,0,sizeof(f));//初始状态（清零） 
		for(ri i=1; i<=d; i++)//阶段 
			for(ri j=w[i]/1000; j<=sum/1000; j++)//决策 
				f[j]=max(f[j],f[j-w[i]/1000]+v[i]);//状态转移
		sum+=f[sum/1000];//累加最大总资产
	}
	cout<<sum;
	return 0;
}