最大约数和

题意

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

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

x 的真约数和

要求这个总贡献最大。

思路

一句话本质：每个整数是一只物品，重量是数字本身、价值是它的真约数和，做 01 背包求最大总价值——数论只是表面，真正的内核是选数约束下最大化的 DP。

先看最直接的暴力：

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，并统计最大真约数和。

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

题目要求"选若干不同的正整数，和不超过 S"，这为什么是背包而不是纯数论？

选数问题的三个约束——每个数只能选一次（01）、总和有上限（容量）、要最大化某个值（价值）——恰好对应 01 背包的全部要素。数论只负责提供"价值"（约数和）的来源，解法仍然靠 DP。

数字本身和它的约数和，在背包模型里分别扮演什么角色？

数字 x 的"重量"是 x（消耗容量），"价值"是 divisor_sum[x]（带来的收益）。一旦预处理出每个数的真约数和，问题就退化成：容量为 S，有 S 个物品，每个物品重量为 x、价值为 divisor_sum[x]，求最大总价值。

约数和怎么预处理？

对每个 [1, S] 内的 x，枚举真因数 d（1 到 x-1 中整除 x 的）累加。高效写法是类似筛法：对每个 d，把它加到所有 d 的倍数上（除了倍数自身）。

DP 转移为什么必须倒序？

设 dp[j] 表示总和不超过 j 时的最大约数和。处理数字 x 时：dp[j] = max(dp[j], dp[j - x] + divisor_sum[x])。如果 j 正序枚举，同一轮内 dp[j - x] 可能已被当前 x 更新过，导致 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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-08 23:13
 * update_at: 2026-08-08 23:13
 * 预处理约数和，01背包选数使约数和最大
 */
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1005;
int s;
int val[maxn];
int dp[maxn];

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

    for (int i = 1; i <= s; ++i) {
        if (i > 1) val[i] = 1;
        for (int d = 2; d * d <= i; ++d) {
            if (i % d) continue;
            val[i] += d;
            if (d * d != i)
                val[i] += i / d;
        }
    }

    for (int i = 1; i <= s; ++i)
        for (int j = s; j >= i; --j)
            dp[j] = max(dp[j], dp[j - i] + val[i]);

    cout << dp[s] << "\n";
    return 0;
}

复杂度

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

总结

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

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

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

一图流解析

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

目录

题意

思路

状态表

DP 公式

代码

复杂度

总结

一图流解析