[NWERC 2004] 投资的最大效益

题意

有一笔初始资金，每一年都可以把钱投到若干种债券里。

每种债券都有：

投资额 a
一年的利息 b

因为投资额都是 1000 的倍数，所以一年的投资方案只和“有多少个 1000 元”有关。每年结束后，利息会并入总资产，下一年可以重新调整投资组合。

这张表把题意翻成了背包模型：

原题对象	背包含义
一种债券	一个可以重复使用的物品
投资额 `a`	物品重量
年利息 `b`	物品价值
一年的总资金	背包容量

思路

先看最直接的暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53#include <bits/stdc++.h>
using namespace std;

struct Bond {
    int cost_unit;
    int profit;
};

int years, types;
long long start_capital;
vector<Bond> bonds;

// 暴力枚举某一年所有可行的投资组合，找这一年的最大利息。
long long brute_one_year(int idx, long long remain_unit, long long current_profit) {
    if (idx == types) {
        return current_profit;
    }

    long long best = current_profit;
    for (long long cnt = 0; cnt * bonds[idx].cost_unit <= remain_unit; cnt++) {
        best = max(best, brute_one_year(idx + 1,
                                        remain_unit - cnt * bonds[idx].cost_unit,
                                        current_profit + cnt * bonds[idx].profit));
    }
    return best;
}

long long dfs_year(int year, long long capital) {
    if (year == years) {
        return capital;
    }

    long long unit = capital / 1000;
    long long best_profit = brute_one_year(0, unit, 0);
    return dfs_year(year + 1, capital + best_profit);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> start_capital >> years >> types;
    bonds.resize(types);
    for (int i = 0; i < types; i++) {
        int cost, profit;
        cin >> cost >> profit;
        bonds[i] = {cost / 1000, profit};
    }

    cout << dfs_year(0, start_capital) << '\n';

    return 0;
}

brute.cpp 先枚举某一年所有可行的投资组合，再把这个过程按年份递归下去。

这个做法正确，但复杂度很高，只适合小数据验证。

关键观察是：

这一年的最优投资方案只和当前资金有关。
债券投资额都是 1000 的倍数，所以可以把资金按 1000 元一档压缩。
每年都要重新做一次“预算内收益最大化”，这正是完全背包。

于是先定义：

best[j] 表示有 j 个 1000 元预算时，这一年最多能拿到多少利息

这张表说明状态定义：

状态	含义
`best[j]`	一年内预算为 `j * 1000` 时的最大利息

对于每种债券：

它可以买很多份，所以是完全背包
转移是 best[j] = max(best[j], best[j - cost] + profit)

DP 公式

每一年都做一次完全背包。设 $best_j$ 表示这一年本金不超过 $j$ 时能获得的最大收益。对每种债券，成本为 $cost_i$ ，收益为 $profit_i$ ：

best_j=\max(best_j,\ best_{j-cost_i}+profit_i)

容量正序枚举。若第 $y$ 年开始时本金为 $money_y$ ，则年底本金变为：

money_{y+1}=money_y+best_{money_y}

每年结算时：

用当前总资产 capital 的千元部分 capital / 1000
查出这一年的最优利息 best[...]
把利息加回总资产，进入下一年

公式解释：每年本金固定后，都要在这个预算内选择债券组合使收益最大。债券可以买多份，所以用完全背包算出当年最大收益，再把收益滚入下一年的本金。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51#include <bits/stdc++.h>
using namespace std;

struct Bond {
    int cost_unit; // 用 1000 为单位后的投资额
    int profit;    // 这一年能拿到的利息
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long capital;
    int years, types;
    cin >> capital >> years >> types;

    vector<Bond> bonds(types);
    for (int i = 0; i < types; i++) {
        int cost, profit;
        cin >> cost >> profit;
        bonds[i] = {cost / 1000, profit};
    }

    // 资本每年最多增长 10%，所以总规模有一个很小的上界。
    // 这里直接按这个上界预处理一年内的最优收益。
    long double upper_capital = capital;
    for (int i = 0; i < years; i++) {
        upper_capital *= 1.1L;
    }
    int max_unit = static_cast<int>(upper_capital / 1000.0L) + 5;
    max_unit = max(max_unit, static_cast<int>(capital / 1000) + 5);

    vector<long long> best(max_unit + 1, 0);

    // 完全背包：在预算为 j 个“千元单位”时，最多能拿到多少利息。
    for (const auto &bond : bonds) {
        for (int j = bond.cost_unit; j <= max_unit; j++) {
            best[j] = max(best[j], best[j - bond.cost_unit] + bond.profit);
        }
    }

    for (int year = 1; year <= years; year++) {
        int unit = static_cast<int>(capital / 1000);
        if (unit > max_unit) unit = max_unit;
        capital += best[unit];
    }

    cout << capital << '\n';

    return 0;
}

复杂度

时间复杂度： $O(n * S + d * S)$ ，其中 S 是按 1000 压缩后的资金上界
空间复杂度： $O(S)$

总结

这题可以拆成两层：

先把“一年内怎么投最赚”做成完全背包
再把这一年的最优收益按年份滚动叠加

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

真正起作用的是“预算按千元压缩”这个观察，它让每年的最优收益表可以直接复用。