数组分割问题(印象深刻)1
需积分: 0 182 浏览量
2022-08-08
23:08:20
上传
评论
收藏 25KB DOCX 举报
【编程之美】数组分割问题
一，问题：
1. 有一个无序、元素个数为 2n 的正整数数组，要求：如何能把这
个数组分割为两个子数组，子数组的元素个数不限，并使两个子数组之
和最接近。
2. 有一个无序、元素个数为 2n 的正整数数组，要求：如何能把这
个数组分割为元素个数为 n 的两个数组，并使两个子数组之和最接近。
二，分析：
假设数组 A[1..2N]所有元素的和是 SUM。模仿动态规划解 0-1 背
包问题的策略，令 S(k, i)表示前 k 个元素中任意 i 个元素的和的集合。
显然：
S(k, 1) = {A[i] | 1<= i <= k}
S(k, k) = {A[1]+A[2]+…+A[k]}
S(k, i) = S(k-1, i) U {A[k] + x | x 属于 S(k-1, i-1) }
按照这个递推公式来计算，最后找出集合 S(2N, N)中与 SUM 最
接近的那个和，这便是答案。这个算法的时间复杂度是 O(2^N).
因为这个过程中只关注和不大于 SUM/2 的那个子数组的和。所
以集合中重复的和以及大于 SUM/2 的和都是没有意义的。把这些没有
意义的和剔除掉，剩下的有意义的和的个数最多就是 SUM/2 个。所以，
我们不需要记录 S(2N,N)中都有哪些和，只需要从 SUM/2 到 1 遍历一
次，逐个询问这个值是不是在 S(2N,N)中出现，第一个出现的值就是答
案。我们的程序不需要按照上述递推公式计算每个集合，只需要为每个
评论0
最新资源