[NWERC 2004] 投资的最大效益

GitHub跳转原题关系图返回列表

先用完全背包求出一年内的最优收益，再按年份滚动更新总资产。

OJ: luogu

题目 ID: P1853

难度:普及

标签:动态规划完全背包背包

创建: 2026-06-19 16:15

更新: 2026-10-07 10:45

前置题目

luogu U661993疯狂的背包问题(11) - 混合背包问题A 讲透并给出代码的「完全背包正序枚举容量即可重复取用同一物品」这一步，被 B 的 main.cpp（第 37 行 for (int j = bond.cost_unit; j <= max_unit; j++)）直接用作一年内求最大利息的完全背包主体；B 在此之上额外叠加了 A 未涉及的按 1000 元压缩预算与按年滚动本金的流程，难度普及+/提高- → 普及+/提高，台阶方向正确。leetcodecn perfect-squares完全平方数B 的某一年解法直接复用 A 的完全背包 dp（容量维 + 可重复物品），只是从最少物品数改成最大收益并在年份上滚动

后置题目

luogu P3891[GDOI2014] 采集资源B 的 gain[x] 预处理正是 A 教的「单期内花预算的最优决策用完全背包 best[j]=max(best[j],best[j-cost]+profit) 压成一张与时间无关的表」这一步（B main.cpp:50 与 A main.cpp:38 同形），A 用它把每年利息滚入下一年本金，B 把它抽成 gain[x] 后再叠加自己新的时间推进 DP（dp[资源]=最大已有采集效率、只保留最大效率的论证），属台阶式叠加而非同难度孪生。luogu P1450[HAOI2008] 硬币购物B 的第一步直接复用 A 教的完全背包状态设计（一维金额数组、物品外层、容量正序枚举即可重复取用），把 A 的 best[j]=max(best[j],best[j-cost]+profit) 换成方案数累加 dp[x]+=dp[x-c]（P1450 main.cpp 第 35-39 行与 A main.cpp 第 38 行同模板）预处理无限硬币的表，随后才叠加 A 未教的 16 子集容斥扣掉超上界方案，属台阶式叠加。

题意

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

每种债券都有：

投资额 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)$

总结

这题可以拆成两层：

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

一图流解析

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

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

P1853 [NWERC 2004] 投资的最大效益

题目背景

约翰先生获得了一大笔遗产，他暂时还用不上这一笔钱，他决定进行投资以获得更大的效益。银行工作人员向他提供了多种债券，每一种债券都能在固定的投资后，提供稳定的年利息。当然，每一种债券的投资额是不同的，一般来说，投资越大，收益也越大，而且，每一年还可以根据资金总额的增加，更换收益更大的债券。

题目描述

例如：有如下两种不同的债券：

投资额 $4000$ ，年利息 $400$ ；
投资额 $3000$ ，年利息 $250$ 。

初始时，有 $10000$ 的总资产，可以投资两份债券 1 债券，一年获得 $800$ 的利息；而投资一份债券 1 和两份债券 2，一年可获得 $900$ 的利息，两年后，可获得 $1800$ 的利息；而所有的资产达到 $11800$ ，然后将卖掉一份债券 2，换购债券 1，年利息可达到 $1050$ ；第三年后，总资产达到 $12850$ ，可以购买三份债券 1，年利息可达到 $1200$ ，第四年后，总资产可达到 $14050$ 。

现给定若干种债券、最初的总资产，帮助约翰先生计算，经过 $n$ 年的投资，总资产的最大值。

输入格式

第一行为三个正整数 $s, n, d$ ，分别表示最初的总资产、年数和债券的种类。

接下来 $d$ 行，每行表示一种债券，两个正整数 $a, b$ 分别表示债券的投资额和年利息。

输出格式

仅一个整数，表示 $n$ 年后的最大总资产。

输入输出样例 #1

输入 #1

text

输出 #1

text

说明/提示

对于 $100 \%$ 的数据， $1 \le s \le {10}^6$ ， $2 \le n \le 40$ ， $1 \le d \le 10$ ， $1 \le a \le {10}^4$ ，且 $a$ 是 $1000$ 的倍数， $b$ 不超过 $a$ 的 $10\%$ 。

[NWERC 2004] 投资的最大效益

目录

题意

思路

DP 公式

代码

复杂度

总结

一图流解析