最大约数和

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

先预处理每个正整数的真约数和，再把数字本身当重量、真约数和当价值，做一维 0/1 背包求最大总价值。

OJ: luogu

题目 ID: P1734

难度:普及-

标签:动态规划01背包背包数论

创建: 2026-06-19 14:53

更新: 2026-10-07 10:45

前置题目
luogu P2639[USACO09OCT] Bessie's Weight Problem GB 主解把 A 教的「一维 dp 内层容量倒序枚举、每件物品最多选一次」原样搬入自己的 main.cpp（for(j=s;j>=i;--j) dp[j]=max(dp[j],dp[j-i]+val[i])），只是先补上真约数和预处理这一步；A 的 dp[j] 状态含义从「容量 j 内最大重量」换成「总和 j 内最大约数和」，模板完全一致。luogu P1060[NOIP 2006 普及组] 开心的金明B 的主解把 A 教的「内层容量倒序枚举、每件至多选一次」一维 0/1 背包原样搬用（main.cpp 的 for (j=s; j>=i; --j) dp[j]=max(dp[j],dp[j-i]+val[i])），只多加真约数和预处理这层题意翻译。luogu P2871[USACO07DEC] Charm Bracelet SB 的主解把 A 教的「内层容量倒序枚举、每件物品至多选一次」原样搬进 main.cpp（for(j=s;j>=i;--j) dp[j]=max(dp[j],dp[j-i]+val[i]) 与 A 的 dp[j]=max(dp[j],dp[j-W[i]]+D[i]) 同形），只把重量价值换成数字与真约数和、并在前面补上真约数和预处理这一额外台阶。
后置题目
roj 3549金明的预算方案B 的一维 knapsack 沿用 A 教的「倒序枚举容量保证每个数字只参与一轮转移」这一具体判定，只是把单个物品换成家族买法选项，使同组方案不被叠加、每组至多选一个；B 在此台阶上再叠加家族内枚举消依赖的新流程。roj 20019食堂打饭B 把 A 教的「一维 01 背包容量倒序枚举、每件至多选一次」原样用在滚动数组 f 上（for j 从 s 递减），只是外层先叠加 b 降序交换论证与「两窗口累计打饭之和 = 前缀和」的一维状态压缩，主解仍是 0/1 背包式转移。luogu P1064[NOIP 2006 提高组] 金明的预算方案B 把 A 教的「一维 dp 内层容量倒序枚举、每件物品至多选一次」原样用于其 main.cpp（for j=n..0 套 dp[j]=max(dp[j],dp[j-cost]+val)），只是把单个物品换成主件+附件枚举出的组合，多出依赖捆绑这一台阶。luogu P2370yyy2015c01 的 U 盘B 的 check(L) 把 A 教的「一维 dp 内层容量倒序枚举、每件物品只选一次」原样搬入（main.cpp 第21-22行 for(j=S;j>=w[i];--j) dp[j]=max(dp[j],dp[j-w[i]]+v[i])），只在外面叠加二分答案与文件大小过滤这一额外台阶。luogu U661995疯狂的背包问题(13) - 分组背包B 的分组背包把 A 教的「容量倒序遍历让物品至多选一次」当作物品层转移规则，再叠加 previous 冻结上一组状态；倒序是 B 每件物品由未选中态转移所必需的步骤，但仅此还不够隔离同组互斥，组内隔离是 B 新增的台阶。luogu U662097疯狂的背包问题(18) - 求最优方案总数B 的主解 main.cpp 直接搬用 A 教的一维 01 背包「容量倒序枚举 dp[c]=max(dp[c],dp[c-v]+w)、每件至多选一次」这一步（B main.cpp:32 for(c=V;c>=v[i];--c) 与 A main.cpp:36 同形），只在其上叠加 cnt 平行数组的『更大覆盖、相等累加』与初值全 1 这一新流程，属台阶式叠加。luogu P1776宝物筛选B 把每个二进制拆分包当 0/1 物品后，直接复用 A 教的「内层容量倒序枚举、每件至多选一次」的一维 01 背包转移（main.cpp 的 for(j=W;j>=wv;j--) dp[j]=max(dp[j],dp[j-wv]+vv)），B 额外叠加的只是拆分出的包数控制与包内重量价值计算。luogu P2340[USACO03FALL] Cow Exhibition GB 主解在智商和状态上复用 A 教的「01 背包按转移方向倒序枚举、保证每件物品至多选一次」这一步（main.cpp 中 iq>=0 分支 for(s=hi;s>=lo;s--) 与 A 的 for(j=s;j>=i;--j) 同型，iq<0 分支才改为正序），并在其上叠加 A 未教的偏移量处理负智商和与双非负约束的收尾。luogu U661996疯狂的背包问题(14) - 有依赖的背包问题B 在合并子节点时沿用 A 教的『容量维倒序枚举、让 dp 从旧状态转移而不重复选取』这一步（main.cpp 的 for (j=V; j>=v[u]; --j) 配 dp[u][j-k]+dp[c][k]），只是把它从一维 0/1 背包搬到树形依赖背包的容量分配合并上，额外叠加 A 未教的依赖树与虚拟根 0，Δrank=1、方向正确。luogu U662012疯狂的背包问题(15) - 泛化物品背包问题B 的一维滚动背包完全照搬 A 教的『容量倒序枚举 + dp[j]=max(dp[j],dp[j-x]+val)』保证每件物品只用一次，只把固定重量换成枚举分配量 x、价值换成插值 val[x] 这一额外台阶luogu U663791疯狂的背包问题(9) - 多重背包问题 IIB 的主解把 A 讲透的「一维 dp 内层容量倒序枚举、每件物品至多选一次」原样当作自己的 0/1 背包主体（B 的 main.cpp 为 for (c=V;c>=pack_v;--c) dp[c]=max(dp[c],dp[c-pack_v]+pack_w)，与 A 的 for (j=s;j>=i;--j) 同形），只是先对每种物品做二进制拆分，把 s_i 件压成 O(log s_i) 个包再套这一步；A 是纯 0/1 背包基础题，B 在其上叠加二进制分组台阶，难度 普及/提高- → 普及+/提高 方向正确。

目录

  1. 题意
  2. 思路
    1. 代码
    2. 复杂度
    3. 总结
    4. 一图流解析

    题意

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

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

    • x 的真约数和

    要求这个总贡献最大。

    思路

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

    先看最直接的暴力：

    cpp
    // 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 公式

    设 gxg_x 表示 xx 的真约数和，dpjdp_j 表示总和不超过 jj 时能得到的最大真约数和。把每个数字 xx 看成一个 0/1 物品：

    dpj=max⁡(dpj, dpj−x+gx) dp_j=\max(dp_j,\ dp_{j-x}+g_x)

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

    dpS dp_S

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

    代码

    cpp
    /**
 * 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(S2)O(S^2)
    • 空间复杂度：O(S)O(S)

    总结

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

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

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

    一图流解析

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

    一图流解析