带权值的最大整除子集（Maximum Sum Divisible Subset）

字数 2290 2025-12-08 20:21:11

带权值的最大整除子集（Maximum Sum Divisible Subset）

题目描述
给定一个无重复正整数数组 nums，你需要找出其中一个最大的子集，使得这个子集中的任意两个元素 a 和 b 都满足 a % b == 0 或 b % a == 0（即一个元素能被另一个整除），并且在满足这个整除关系的基础上，使得子集的权值和最大。其中，每个元素的权值就是其本身的数值。你需要返回这个最大权值和。

例如：

输入：nums = [3, 5, 10, 20, 21]
最大整除子集（权值和最大）可能是 [5, 10, 20]，其和为 35。
输入：nums = [1, 2, 4, 8, 16]
最大整除子集是其本身，和为 31。

注意：子集不需要是连续的，只需保持原数组的顺序即可（但排序后不影响整除关系的判断）。

解题思路
这个问题是经典“最大整除子集”的变种，原题只要求最大子集的长度，这里我们要求最大权值和。核心思想仍然是动态规划，但状态转移和状态表示需要调整。

步骤分解

第一步：预处理排序
因为整除关系要求任意两数之间能整除，这通常意味着如果我们对数组排序，那么只需要检查较小数能否整除较大数（因为若 a <= b，则 a % b == 0 仅在 a == b 时成立，但题目是任意两个数，实际我们只考虑 b % a == 0 当 a <= b 时）。
所以，将数组升序排序后，我们只需保证对于排序后的数组，子集中前面的数能整除后面的数，这样就自动满足任意两数可整除。
注意：排序后不影响子集的选择，我们只需要在原数组顺序中找出满足整除关系的任意子集即可。

第二步：定义状态
定义 dp[i] 表示：以第 i 个元素（排序后）为子集的最后一个（即最大）元素时，所能得到的最大整除子集的权值和。
注意：这里和传统最大整除子集类似，但传统记录长度，这里记录权值和。
初始时，dp[i] = nums[i]，因为至少可以只包含自己。

第三步：状态转移
对于每个 i，我们查看它之前的所有 j (0 <= j < i)，如果 nums[i] % nums[j] == 0，那么 nums[i] 可以接在以 nums[j] 结尾的整除子集后面，形成一个新的整除子集。
此时新的权值和为 dp[j] + nums[i]。
我们取所有满足条件的 j 中，dp[j] + nums[i] 的最大值，来更新 dp[i]。
即：

\[dp[i] = \max(dp[i], \; dp[j] + nums[i]) \quad \text{其中} \; j < i \; \text{且} \; nums[i] \% nums[j] == 0 \]

这个转移方程的意思是：如果 nums[i] 能整除 nums[j]，那么我们可以把 nums[i] 加到以 nums[j] 结尾的子集后面，权值和相应增加。

第四步：计算最终答案
最终答案并不是 dp[n-1]，因为最大权值和子集不一定以最后一个元素结尾。
我们需要取所有 dp[i] 的最大值：

\[\text{answer} = \max_{0 \le i < n} dp[i] \]

这表示考虑所有可能的结尾元素，取权值和最大的那个。

第五步：例子推演
以 nums = [3, 5, 10, 20, 21] 为例：
排序后得到 [3, 5, 10, 20, 21]（已有序）。

初始化：dp = [3, 5, 10, 20, 21]

i=0：前面没有数，保持 dp[0]=3
i=1：检查 j=0，5%3≠0，无法接在后面，保持 dp[1]=5
i=2：检查 j=0，10%3≠0；j=1，10%5==0，可以接在5后面，dp[2]=max(10, dp[1]+10=5+10=15)=15
i=3：检查 j=0，20%3≠0；j=1，20%5==0，可接在5后面，dp[3]=max(20, dp[1]+20=5+20=25)=25；
检查 j=2，20%10==0，可接在10后面，dp[3]=max(25, dp[2]+20=15+20=35)=35
i=4：检查 j=0，21%3==0，dp[4]=max(21, dp[0]+21=3+21=24)=24；
检查 j=1，21%5≠0；j=2，21%10≠0；j=3，21%20≠0，最终 dp[4]=24

最终 dp = [3, 5, 15, 35, 24]，最大值为 35，即所求。

第六步：扩展（如果需要输出具体子集）
题目只要求权值和，但如果需要输出具体子集，可以在动态规划时记录“前驱节点”，即从哪个 j 转移过来的。然后从最大 dp[i] 的 i 开始，往前回溯，得到子集元素。

算法复杂度
排序 O(n log n)，动态规划双层循环 O(n²)，总时间复杂度 O(n²)，空间复杂度 O(n)（存储 dp 数组）。

核心要点

排序让整除判断变成单向的（前面整除后面），简化问题。
dp[i] 表示以 nums[i] 结尾的最大整除子集权值和。
状态转移时，检查 nums[i] 是否能被前面的某个 nums[j] 整除，若能，则尝试扩展。
最终答案取所有 dp[i] 的最大值。

带权值的最大整除子集（Maximum Sum Divisible Subset）题目描述给定一个无重复正整数数组 nums ，你需要找出其中一个最大的子集，使得这个子集中的任意两个元素 a 和 b 都满足 a % b == 0 或 b % a == 0 （即一个元素能被另一个整除），并且在满足这个整除关系的基础上，使得子集的权值和最大。其中，每个元素的权值就是其本身的数值。你需要返回这个最大权值和。例如：输入： nums = [3, 5, 10, 20, 21] 最大整除子集（权值和最大）可能是 [5, 10, 20] ，其和为 35。输入： nums = [1, 2, 4, 8, 16] 最大整除子集是其本身，和为 31。注意：子集不需要是连续的，只需保持原数组的顺序即可（但排序后不影响整除关系的判断）。解题思路这个问题是经典“最大整除子集”的变种，原题只要求最大子集的长度，这里我们要求最大权值和。核心思想仍然是动态规划，但状态转移和状态表示需要调整。步骤分解第一步：预处理排序因为整除关系要求任意两数之间能整除，这通常意味着如果我们对数组排序，那么只需要检查较小数能否整除较大数（因为若 a <= b ，则 a % b == 0 仅在 a == b 时成立，但题目是任意两个数，实际我们只考虑 b % a == 0 当 a <= b 时）。所以，将数组升序排序后，我们只需保证对于排序后的数组，子集中前面的数能整除后面的数，这样就自动满足任意两数可整除。注意：排序后不影响子集的选择，我们只需要在原数组顺序中找出满足整除关系的任意子集即可。第二步：定义状态定义 dp[i] 表示：以第 i 个元素（排序后）为子集的最后一个（即最大）元素时，所能得到的最大整除子集的权值和。注意：这里和传统最大整除子集类似，但传统记录长度，这里记录权值和。初始时， dp[i] = nums[i] ，因为至少可以只包含自己。第三步：状态转移对于每个 i ，我们查看它之前的所有 j (0 <= j < i) ，如果 nums[i] % nums[j] == 0 ，那么 nums[i] 可以接在以 nums[j] 结尾的整除子集后面，形成一个新的整除子集。此时新的权值和为 dp[j] + nums[i] 。我们取所有满足条件的 j 中， dp[j] + nums[i] 的最大值，来更新 dp[i] 。即： \[ dp[ i] = \max(dp[ i], \; dp[ j] + nums[ i]) \quad \text{其中} \; j < i \; \text{且} \; nums[ i] \% nums[ j ] == 0 \] 这个转移方程的意思是：如果 nums[i] 能整除 nums[j] ，那么我们可以把 nums[i] 加到以 nums[j] 结尾的子集后面，权值和相应增加。第四步：计算最终答案最终答案并不是 dp[n-1] ，因为最大权值和子集不一定以最后一个元素结尾。我们需要取所有 dp[i] 的最大值： \[ \text{answer} = \max_ {0 \le i < n} dp[ i ] \] 这表示考虑所有可能的结尾元素，取权值和最大的那个。第五步：例子推演以 nums = [3, 5, 10, 20, 21] 为例：排序后得到 [3, 5, 10, 20, 21] （已有序）。初始化： dp = [3, 5, 10, 20, 21] i=0：前面没有数，保持 dp[ 0 ]=3 i=1：检查 j=0，5%3≠0，无法接在后面，保持 dp[ 1 ]=5 i=2：检查 j=0，10%3≠0；j=1，10%5==0，可以接在5后面，dp[ 2]=max(10, dp[ 1 ]+10=5+10=15)=15 i=3：检查 j=0，20%3≠0；j=1，20%5==0，可接在5后面，dp[ 3]=max(20, dp[ 1 ]+20=5+20=25)=25；检查 j=2，20%10==0，可接在10后面，dp[ 3]=max(25, dp[ 2 ]+20=15+20=35)=35 i=4：检查 j=0，21%3==0，dp[ 4]=max(21, dp[ 0 ]+21=3+21=24)=24；检查 j=1，21%5≠0；j=2，21%10≠0；j=3，21%20≠0，最终 dp[ 4 ]=24 最终 dp = [ 3, 5, 15, 35, 24 ]，最大值为 35，即所求。第六步：扩展（如果需要输出具体子集）题目只要求权值和，但如果需要输出具体子集，可以在动态规划时记录“前驱节点”，即从哪个 j 转移过来的。然后从最大 dp[ i ] 的 i 开始，往前回溯，得到子集元素。算法复杂度排序 O(n log n)，动态规划双层循环 O(n²)，总时间复杂度 O(n²)，空间复杂度 O(n)（存储 dp 数组）。核心要点排序让整除判断变成单向的（前面整除后面），简化问题。 dp[ i] 表示以 nums[ i ] 结尾的最大整除子集权值和。状态转移时，检查 nums[ i] 是否能被前面的某个 nums[ j ] 整除，若能，则尝试扩展。最终答案取所有 dp[ i ] 的最大值。