最大约数和

题意

从若干个不同的正整数里选数，使它们的和不超过 S。

对每个被选中的数 x，它会贡献：

x 的真约数和

要求这个总贡献最大。

思路

先看最直接的暴力：

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
54
55
56
57
58
59
60
61
62
63
64
65// brute.cpp：小数据暴力解，使用 01 序列枚举每个正整数选或不选。
#include <bits/stdc++.h>
using namespace std;

const int MAXS = 1005;

int s;                  // 总和上限
int divisor_sum[MAXS];  // 真约数和
int choose_num[MAXS];   // choose_num[i] = 0/1，表示数字 i 不选/选
int best_answer;        // 当前最大约数和

void build_divisor_sum() {
    memset(divisor_sum, 0, sizeof(divisor_sum));
    for (int d = 1; d <= s / 2; d++) {
        for (int multiple = d + d; multiple <= s; multiple += d) {
            divisor_sum[multiple] += d;
        }
    }
}

bool check() {
    int sum_weight = 0;
    for (int i = 1; i <= s; i++) {
        if (choose_num[i] == 1) sum_weight += i;
    }
    return sum_weight <= s;
}

int calc_answer() {
    int sum_value = 0;
    for (int i = 1; i <= s; i++) {
        if (choose_num[i] == 1) sum_value += divisor_sum[i];
    }
    return sum_value;
}

void dfs_choose(int dep) {
    if (dep == s + 1) {
        if (check()) {
            int value = calc_answer();
            if (best_answer < value) best_answer = value;
        }
        return;
    }

    // 第 dep 个正整数的 01 选择：0 不选，1 选。
    for (int i = 0; i <= 1; i++) {
        choose_num[dep] = i;
        dfs_choose(dep + 1);
    }
}

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

    cin >> s;
    build_divisor_sum();

    best_answer = 0;
    dfs_choose(1);

    cout << best_answer << '\n';
    return 0;
}

brute.cpp 把每个正整数看成一个 01 选择：choose_num[i] = 0/1 表示不选或选。递归先生成完整选择，叶子节点再检查总和是否不超过 S，并统计最大真约数和。

这个做法能帮助理解题意，但复杂度是指数级，无法用于正式数据。

关键观察是：题目虽然表面上带有数论味道，但真正的核心只有两步：

先算出每个数的真约数和
再做一个 0/1 背包

具体来说，把每个整数 x 看成一个物品：

重量：x
价值：divisor_sum[x]

这样题目就变成了：

背包容量是 S
每个数字最多选一次
求最大总价值

设：

dp[j] 表示总和不超过 j 时的最大约数和

转移是：

dp[j] = max(dp[j], dp[j - x] + divisor_sum[x])

由于每个数字只能选一次，容量维必须倒序枚举。

状态表

这张表说明建模后的状态含义：

状态	含义
`dp[j]`	总和不超过 `j` 时的最大约数和

这里真正重要的是先完成题意翻译：数字本身是“重量”，真约数和是“价值”。一旦翻译出来，后面就是标准一维 0/1 背包。

最后输出 dp[S] 即可。

DP 公式

设 $g_x$ 表示 $x$ 的真约数和， $dp_j$ 表示总和不超过 $j$ 时能得到的最大真约数和。把每个数字 $x$ 看成一个 0/1 物品：

dp_j=\max(dp_j,\ dp_{j-x}+g_x)

其中 $j\geqslant x$ ，并且容量倒序枚举。最终答案为：

dp_S

公式解释：选数字 x 会消耗总和容量 x，带来真约数和收益 g_x。每个数字最多选一次，因此是标准 0/1 背包最大收益转移。

代码

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#include <bits/stdc++.h>
using namespace std;

const int MAXS = 1005;

int s;                  // 总和上限
int divisor_sum[MAXS];  // divisor_sum[i] = i 的真约数和
int dp[MAXS];           // dp[j] = 和不超过 j 时的最大约数和

void read_input() {
    cin >> s;
}

void build_divisor_sum() {
    memset(divisor_sum, 0, sizeof(divisor_sum));
    for (int d = 1; d <= s / 2; d++) {
        for (int multiple = d + d; multiple <= s; multiple += d) {
            divisor_sum[multiple] += d;
        }
    }
}

void solve() {
    build_divisor_sum();
    memset(dp, 0, sizeof(dp));

    for (int x = 1; x <= s; x++) {
        // 每个正整数只能选一次，所以按 0/1 背包倒序枚举。
        for (int j = s; j >= x; j--) {
            dp[j] = max(dp[j], dp[j - x] + divisor_sum[x]);
        }
    }

    cout << dp[s] << '\n';
}

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

    read_input();
    solve();

    return 0;
}

复杂度

时间复杂度： $O(S^2)$
空间复杂度： $O(S)$

总结

这题的关键不在背包，而在题意翻译：

先把每个数的真约数和预处理出来
再把它看成一个普通的 0/1 物品

很多“数论 + 最优选择”的题，最后落地时其实还是熟悉的动态规划模型。

一图流解析

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

目录

题意

思路

状态表

DP 公式

代码

复杂度

总结

一图流解析