带限制的最大整除子集（Maximum Sum Divisible Subset with Constraints）

字数 4276 2025-12-09 23:00:15

带限制的最大整除子集（Maximum Sum Divisible Subset with Constraints）

题目描述
给定一个无重复元素的正整数数组 nums 和一个正整数 k。你需要找到数组的一个子集（不要求连续），使得子集中任意两个元素 a 和 b 都满足 a % b == 0 或 b % a == 0（即一个能被另一个整除），同时要求子集中所有元素的和是 k 的倍数。目标是找到满足这些条件的子集的最大和。如果不存在这样的子集，则返回 0。

例如：
nums = [1, 2, 4, 6, 8], k = 3
一个满足条件的子集是 [2, 4, 8]（任意两元素可整除，且和 14 不是 3 的倍数，不满足）。但子集 [1, 2, 6] 满足整除条件，和 9 是 3 的倍数，因此是有效子集，和为 9。实际上最大和是 12（子集 [2, 4, 6]，任意两元素可整除，和 12 是 3 的倍数）。注意子集 [2, 4, 6] 中 4 和 6 不满足整除条件（4 不能整除 6，6 也不能整除 4），因此这个例子中我们需要重新审视。我们先给出一个正确例子：
nums = [1, 2, 3, 6], k = 4
子集 [1, 2, 3, 6] 中任意两元素不一定可整除（比如 2 和 3 不满足），所以不行。子集 [1, 2, 6] 满足整除条件（1 整除 2, 1 整除 6, 2 整除 6），和 9 对 4 取模为 1，不是倍数。子集 [1, 3, 6] 满足整除条件，和 10 对 4 取模为 2，也不是倍数。子集 [2, 6] 满足整除条件，和 8 是 4 的倍数，和为 8。更大子集 [1, 2, 3] 不满足整除条件（2 和 3 不整除）。所以最大和是 8。

解题思路
这个问题结合了“最大整除子集”（原题是找最长长度，这里找最大和，且增加和是 k 的倍数的条件）和“子集和模 k”的限制。
我们可以用动态规划来解决，但需要巧妙地设计状态。

关键观察：

整除关系具有传递性：如果 a|b 且 b|c，则 a|c。因此，如果我们将数组按升序排序，那么一个满足“任意两元素可整除”的子集，一定满足：对排序后的子集，每个元素都是它前面某个元素的倍数。
因此，问题转化为：在排序后的数组中，选择一个递增子序列（不要求连续），使得序列中每个元素都是前一个元素的倍数（实际上更宽松：只要序列中任意两元素可整除，在排序后等价于每个元素都是它前面所有元素的倍数？不一定，比如 [2,4,6] 排序后 4 是 2 的倍数，但 6 不是 4 的倍数，所以 4 和 6 不满足整除，因此这个序列就不合法）。所以更准确地说，在排序后的数组中，一个子集满足任意两元素可整除，当且仅当最小元素能整除所有其他元素（因为整除性不满足对称性，但子集中任取两个，必须一个整除另一个。在排序后的子集中，最小的数必须能整除所有比它大的数，否则存在一对不满足整除）。
证明：设子集中最小为 m，对任意 x>m，若 m 不整除 x，则它们不满足整除条件（因为 x 也不一定整除 m，比如 m=4,x=6）。所以必要条件是最小元素能整除所有其他元素。然后检查是否充分：如果最小元素 m 整除所有其他元素，那么对任意两个元素 a,b（a<b），有 m|a 且 m|b，但 a 不一定整除 b。例如 m=2, a=4, b=6，2|4,2|6，但 4 不整除 6，6 不整除 4，所以 a 和 b 不满足整除条件。因此仅最小元素整除所有元素还不够。实际上，要满足任意两元素可整除，必须满足：排序后的子集中，每个元素都是它前面那个元素的倍数（递推），因为整除性不传递到非相邻元素？让我们严格分析：
集合 S 排序后为 s1 < s2 < ... < st。
条件：∀i<j，要么 si|sj 要么 sj|si。
因为 si<sj，所以只可能是 si|sj。
因此必须有 s1|s2, s1|s3, ..., s1|st。
但还需 s2|s3 吗？取 i=2,j=3，需要 s2|s3。
所以相邻的也必须满足整除。
归纳可得：si|si+1 对所有 i 成立。
反过来，如果相邻满足整除，则传递性可得任意 si|sj (i<j)。
所以充要条件是：排序后的子序列中，每个元素是前一个元素的倍数。

因此，我们可以在排序后的数组上，类似“最长递增子序列”那样做 DP，但转移条件不是数值递增，而是“前一个元素能整除当前元素”。

我们需要子集的和是 k 的倍数。这可以通过在 DP 状态中记录“和模 k 的余数”来实现。

动态规划定义
设数组已升序排序。
定义 dp[i][r]：考虑前 i 个元素（以第 i 个元素为子集的最后一个元素），且子集的总和模 k 的余数为 r 时的最大和。
如果不存在这样的子集，则 dp[i][r] = -∞。

转移方程：
对于每个 i，我们可以：

单独以 nums[i] 作为一个子集：此时和模 k 的余数为 nums[i] % k，和就是 nums[i]。
所以 dp[i][nums[i] % k] = max(dp[i][nums[i] % k], nums[i])。
尝试将 nums[i] 接到某个前面的元素 nums[j] (j < i) 后面，要求 nums[j] 能整除 nums[i]。
设加入 nums[i] 前，以 nums[j] 结尾的子集和模 k 的余数为 r'，则加入 nums[i] 后新的和模 k 的余数为 (r' + nums[i]) % k。
新的和 = 旧的和 + nums[i]。
所以 dp[i][(r' + nums[i]) % k] = max(dp[i][(r' + nums[i]) % k], dp[j][r'] + nums[i])，其中 r' 从 0 到 k-1。

初始化：dp[i][r] 初始为 -∞（用一个大负数表示不可能状态）。
最终答案：所有 dp[i][0] 的最大值（模 k 余 0 表示和是 k 的倍数）。如果所有都是 -∞，则答案为 0。

具体步骤

对 nums 进行升序排序。
初始化二维数组 dp[n][k]，全部填充为负无穷（比如 -1e9）。
遍历 i 从 0 到 n-1：
- 首先，单独以 nums[i] 作为一个子集：dp[i][nums[i] % k] = max(dp[i][nums[i] % k], nums[i])。
- 然后，遍历 j 从 0 到 i-1：
  - 如果 nums[j] 能整除 nums[i]（即 nums[i] % nums[j] == 0）：
    - 对于所有余数 r' 从 0 到 k-1：
      - 如果 dp[j][r'] 不是负无穷（表示以 nums[j] 结尾、余数为 r' 的子集存在）：
        
        新余数 r_new = (r' + nums[i]) % k
        
        新和 = dp[j][r'] + nums[i]
        
        更新 dp[i][r_new] = max(dp[i][r_new], dp[j][r'] + nums[i])
遍历所有 i 和 r=0 的状态，取最大值作为答案。如果所有 dp[i][0] 都是负无穷，返回 0。

例子推演
nums = [1, 2, 3, 6], k = 4
排序后为 [1, 2, 3, 6]。

i=0, num=1:
单独子集：dp[0][1%4=1] = max(-∞,1)=1。

i=1, num=2:
单独子集：dp[1][2%4=2]=2。
检查 j=0: 1|2 成立，从 dp[0][1]=1 转移：新余数 (1+2)%4=3，新和=1+2=3，dp[1][3]=max(-∞,3)=3。

i=2, num=3:
单独子集：dp[2][3%4=3]=3。
检查 j=0: 1|3 成立，从 dp[0][1]=1 转移：新余数 (1+3)%4=0，新和=1+3=4，dp[2][0]=4。
检查 j=1: 2 不整除 3，跳过。

i=3, num=6:
单独子集：dp[3][6%4=2]=6。
检查 j=0: 1|6 成立，从 dp[0][1]=1 转移：新余数 (1+6)%4=3，新和=1+6=7，dp[3][3]=7。
检查 j=1: 2|6 成立，从 dp[1][2]=2 转移：新余数 (2+6)%4=0，新和=2+6=8，dp[3][0]=8。
从 dp[1][3]=3 转移：新余数 (3+6)%4=1，新和=3+6=9，dp[3][1]=9。
检查 j=2: 3|6 成立，从 dp[2][0]=4 转移：新余数 (0+6)%4=2，新和=4+6=10，dp[3][2]=10。
从 dp[2][3]=3 转移：新余数 (3+6)%4=1，新和=3+6=9，dp[3][1]=max(9,9)=9。

最终看 dp[?][0]：
dp[0][0] 不存在，dp[1][0] 不存在，dp[2][0]=4，dp[3][0]=8。
最大值为 8，对应子集 [2,6]（和 8 是 4 的倍数，且 2|6）。

复杂度分析

排序 O(n log n)。
DP 状态数 O(nk)，转移时对每个 i 遍历 j 和余数 r'，复杂度 O(nkn) = O(n²k)。
空间 O(n*k)。

优化
整除条件 nums[j]|nums[i] 意味着 nums[j] 是 nums[i] 的因子。我们可以预处理每个数的因子列表，这样枚举 j 时只需枚举 nums[i] 的因子对应的索引，减少 j 的遍历次数。但因子数目一般不大，优化后接近 O(nksqrt(max(nums)))。

总结
这道题是最大整除子集与子集和模 k 限制的结合。核心在于排序后，整除子集等价于相邻元素满足整除关系的序列，因此可以用类似 LIS 的 DP 来构建。在状态中加入“和模 k 的余数”即可处理倍数限制。最终目标是所有余数为 0 的状态中的最大和。

带限制的最大整除子集（Maximum Sum Divisible Subset with Constraints）题目描述给定一个无重复元素的正整数数组 nums 和一个正整数 k 。你需要找到数组的一个子集（不要求连续），使得子集中任意两个元素 a 和 b 都满足 a % b == 0 或 b % a == 0 （即一个能被另一个整除），同时要求子集中所有元素的和是 k 的倍数。目标是找到满足这些条件的子集的最大和。如果不存在这样的子集，则返回 0。例如： nums = [1, 2, 4, 6, 8] , k = 3 一个满足条件的子集是 [2, 4, 8] （任意两元素可整除，且和 14 不是 3 的倍数，不满足）。但子集 [1, 2, 6] 满足整除条件，和 9 是 3 的倍数，因此是有效子集，和为 9。实际上最大和是 12（子集 [2, 4, 6] ，任意两元素可整除，和 12 是 3 的倍数）。注意子集 [2, 4, 6] 中 4 和 6 不满足整除条件（4 不能整除 6，6 也不能整除 4），因此这个例子中我们需要重新审视。我们先给出一个正确例子： nums = [1, 2, 3, 6] , k = 4 子集 [1, 2, 3, 6] 中任意两元素不一定可整除（比如 2 和 3 不满足），所以不行。子集 [1, 2, 6] 满足整除条件（1 整除 2, 1 整除 6, 2 整除 6），和 9 对 4 取模为 1，不是倍数。子集 [1, 3, 6] 满足整除条件，和 10 对 4 取模为 2，也不是倍数。子集 [2, 6] 满足整除条件，和 8 是 4 的倍数，和为 8。更大子集 [1, 2, 3] 不满足整除条件（2 和 3 不整除）。所以最大和是 8。解题思路这个问题结合了“最大整除子集”（原题是找最长长度，这里找最大和，且增加和是 k 的倍数的条件）和“子集和模 k”的限制。我们可以用动态规划来解决，但需要巧妙地设计状态。关键观察：整除关系具有传递性：如果 a|b 且 b|c，则 a|c。因此，如果我们将数组按升序排序，那么一个满足“任意两元素可整除”的子集，一定满足：对排序后的子集，每个元素都是它前面某个元素的倍数。因此，问题转化为：在排序后的数组中，选择一个递增子序列（不要求连续），使得序列中每个元素都是前一个元素的倍数（实际上更宽松：只要序列中任意两元素可整除，在排序后等价于每个元素都是它前面所有元素的倍数？不一定，比如 [ 2,4,6] 排序后 4 是 2 的倍数，但 6 不是 4 的倍数，所以 4 和 6 不满足整除，因此这个序列就不合法）。所以更准确地说，在排序后的数组中，一个子集满足任意两元素可整除，当且仅当最小元素能整除所有其他元素（因为整除性不满足对称性，但子集中任取两个，必须一个整除另一个。在排序后的子集中，最小的数必须能整除所有比它大的数，否则存在一对不满足整除）。证明：设子集中最小为 m，对任意 x>m，若 m 不整除 x，则它们不满足整除条件（因为 x 也不一定整除 m，比如 m=4,x=6）。所以必要条件是最小元素能整除所有其他元素。然后检查是否充分：如果最小元素 m 整除所有其他元素，那么对任意两个元素 a,b（a <b），有 m|a 且 m|b，但 a 不一定整除 b。例如 m=2, a=4, b=6，2|4,2|6，但 4 不整除 6，6 不整除 4，所以 a 和 b 不满足整除条件。因此仅最小元素整除所有元素还不够。实际上，要满足任意两元素可整除，必须满足：排序后的子集中，每个元素都是它前面那个元素的倍数（递推），因为整除性不传递到非相邻元素？让我们严格分析：集合 S 排序后为 s1 < s2 < ... < st。条件：∀i <j，要么 si|sj 要么 sj|si。因为 si <sj，所以只可能是 si|sj。因此必须有 s1|s2, s1|s3, ..., s1|st。但还需 s2|s3 吗？取 i=2,j=3，需要 s2|s3。所以相邻的也必须满足整除。归纳可得：si|si+1 对所有 i 成立。反过来，如果相邻满足整除，则传递性可得任意 si|sj (i <j)。所以充要条件是：排序后的子序列中，每个元素是前一个元素的倍数。因此，我们可以在排序后的数组上，类似“最长递增子序列”那样做 DP，但转移条件不是数值递增，而是“前一个元素能整除当前元素”。我们需要子集的和是 k 的倍数。这可以通过在 DP 状态中记录“和模 k 的余数”来实现。动态规划定义设数组已升序排序。定义 dp[i][r] ：考虑前 i 个元素（以第 i 个元素为子集的最后一个元素），且子集的总和模 k 的余数为 r 时的最大和。如果不存在这样的子集，则 dp[i][r] = -∞ 。转移方程：对于每个 i，我们可以：单独以 nums[ i] 作为一个子集：此时和模 k 的余数为 nums[i] % k ，和就是 nums[ i ]。所以 dp[i][nums[i] % k] = max(dp[i][nums[i] % k], nums[i]) 。尝试将 nums[ i] 接到某个前面的元素 nums[ j] (j < i) 后面，要求 nums[ j] 能整除 nums[ i ]。设加入 nums[ i] 前，以 nums[ j] 结尾的子集和模 k 的余数为 r'，则加入 nums[ i] 后新的和模 k 的余数为 (r' + nums[i]) % k 。新的和 = 旧的和 + nums[ i ]。所以 dp[i][(r' + nums[i]) % k] = max(dp[i][(r' + nums[i]) % k], dp[j][r'] + nums[i]) ，其中 r' 从 0 到 k-1。初始化： dp[i][r] 初始为 -∞（用一个大负数表示不可能状态）。最终答案：所有 dp[i][0] 的最大值（模 k 余 0 表示和是 k 的倍数）。如果所有都是 -∞，则答案为 0。具体步骤对 nums 进行升序排序。初始化二维数组 dp[n][k] ，全部填充为负无穷（比如 -1e9）。遍历 i 从 0 到 n-1：首先，单独以 nums[ i] 作为一个子集： dp[i][nums[i] % k] = max(dp[i][nums[i] % k], nums[i]) 。然后，遍历 j 从 0 到 i-1：如果 nums[ j] 能整除 nums[ i]（即 nums[ i] % nums[ j ] == 0）：对于所有余数 r' 从 0 到 k-1：如果 dp[j][r'] 不是负无穷（表示以 nums[ j ] 结尾、余数为 r' 的子集存在）：新余数 r_ new = (r' + nums[ i ]) % k 新和 = dp[j][r'] + nums[i] 更新 dp[i][r_new] = max(dp[i][r_new], dp[j][r'] + nums[i]) 遍历所有 i 和 r=0 的状态，取最大值作为答案。如果所有 dp[ i][ 0 ] 都是负无穷，返回 0。例子推演 nums = [ 1, 2, 3, 6 ], k = 4 排序后为 [ 1, 2, 3, 6 ]。 i=0, num=1: 单独子集：dp[ 0][ 1%4=1 ] = max(-∞,1)=1。 i=1, num=2: 单独子集：dp[ 1][ 2%4=2 ]=2。检查 j=0: 1|2 成立，从 dp[ 0][ 1]=1 转移：新余数 (1+2)%4=3，新和=1+2=3，dp[ 1][ 3 ]=max(-∞,3)=3。 i=2, num=3: 单独子集：dp[ 2][ 3%4=3 ]=3。检查 j=0: 1|3 成立，从 dp[ 0][ 1]=1 转移：新余数 (1+3)%4=0，新和=1+3=4，dp[ 2][ 0 ]=4。检查 j=1: 2 不整除 3，跳过。 i=3, num=6: 单独子集：dp[ 3][ 6%4=2 ]=6。检查 j=0: 1|6 成立，从 dp[ 0][ 1]=1 转移：新余数 (1+6)%4=3，新和=1+6=7，dp[ 3][ 3 ]=7。检查 j=1: 2|6 成立，从 dp[ 1][ 2]=2 转移：新余数 (2+6)%4=0，新和=2+6=8，dp[ 3][ 0 ]=8。从 dp[ 1][ 3]=3 转移：新余数 (3+6)%4=1，新和=3+6=9，dp[ 3][ 1 ]=9。检查 j=2: 3|6 成立，从 dp[ 2][ 0]=4 转移：新余数 (0+6)%4=2，新和=4+6=10，dp[ 3][ 2 ]=10。从 dp[ 2][ 3]=3 转移：新余数 (3+6)%4=1，新和=3+6=9，dp[ 3][ 1 ]=max(9,9)=9。最终看 dp[ ?][ 0 ]： dp[ 0][ 0] 不存在，dp[ 1][ 0] 不存在，dp[ 2][ 0]=4，dp[ 3][ 0 ]=8。最大值为 8，对应子集 [ 2,6 ]（和 8 是 4 的倍数，且 2|6）。复杂度分析排序 O(n log n)。 DP 状态数 O(n k)，转移时对每个 i 遍历 j 和余数 r'，复杂度 O(n k n) = O(n² k)。空间 O(n* k)。优化整除条件 nums[ j]|nums[ i] 意味着 nums[ j] 是 nums[ i] 的因子。我们可以预处理每个数的因子列表，这样枚举 j 时只需枚举 nums[ i] 的因子对应的索引，减少 j 的遍历次数。但因子数目一般不大，优化后接近 O(n k sqrt(max(nums)))。总结这道题是最大整除子集与子集和模 k 限制的结合。核心在于排序后，整除子集等价于相邻元素满足整除关系的序列，因此可以用类似 LIS 的 DP 来构建。在状态中加入“和模 k 的余数”即可处理倍数限制。最终目标是所有余数为 0 的状态中的最大和。