P1853 投资的最大效益

P1853 投资的最大效益

精心包装的背包.

既然债券可以随时买卖,那么就不需要记录什么买卖与否的状态,直接对于每一年选择买还是不买就行了,并且在当年由此直接获得利息,利息直接加到总资产上面,不用考虑本金存取的问题,转化为完全背包问题.

应该注意到,这里的n年是一个模板外的东西,先解决模板部分.

for(int j = 0; j < d; j++)
            for(int k = w[j]; k <= s; k++)
                dp[k] = max(dp[k], dp[k - w[j]] + v[j]);

这样可以求出dp[s],即以s为初始资产在一年后可得最大资产.

 现在,你只需要:

s += dp[s];

并且再次执行模板里的内容就可以得到一年后的一年后的最大资产,显然这样下去就可以得出n年后的最大资产的正确值.

这里,每一年的循环开始前是否需要重置一下dp数组为0呢?

设上一年初始资金为a,今年初始资金为b,

你可以想象到,从第二年起,dp[k]存储的值总是上一年在拥有资金k时可得的最大收益,而k的范围是0~a,今年你将要计算的范围在0~b,

而这两年(以及之后任意一年)的0~a的计算方法是完全一样的,也就是说今年dp数组的初始状态在0~a部分已经计算好了,剩下的是a~b的计算.

这时候会有什么影响呢?你会发现没有影响,结合完全背包的特性去思考,dp[k] = max(dp[k], dp[k - w[j]] + v[j])

总是会取dp[k] = dp[k].

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int s, n, d, w[50], v[50], dp[10000010];

int main(){
    cin >> s >> n >> d;
    for(int i = 0; i < d; i++) cin >> w[i] >> v[i];

    // dp[0] = s;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < d; j++)
            for(int k = w[j]; k <= s; k++)
                dp[k] = max(dp[k], dp[k - w[j]] + v[j]);
        s += dp[s];
    }

    cout << s << endl;

    return 0;
}

/* 
dp[i][j]   前i种债券 j资产 最大收益
dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);

 */