r*****e 发帖数: 146 | 1 不会啊,上来请教一下。
Given an unsorted array, how to divide them into two equal arrays whose
difference of sum is minimum in O(n) time? |
c**s 发帖数: 159 | 2 NP-hard...
一般做法是dp 枚举之类的 |
e****e 发帖数: 418 | |
h****n 发帖数: 1093 | 4 DP..只不过是三维的DP
设F[i][j][k]表示前i个元素中选取j个元素,使得其和不超过k且最接近k。那
么可以根据第i个元素是否选择来进行决策
状态方程如下:
F[i][j][k]=max{F[i-1][j][k],F[i-1][j-1][k-A[i]]+A[i] }
【在 r*****e 的大作中提到】 : 不会啊,上来请教一下。 : Given an unsorted array, how to divide them into two equal arrays whose : difference of sum is minimum in O(n) time?
|
h****n 发帖数: 1093 | 5 坊间其实还有一种贪心算法,不过不知道正确性,你可以参考参考
先对数组进行排序,然后用动态规划思想,逐步添加。 O(nlogn)
每次读两个,一共n/2次循环,每次循环中的和计算可以累加
初始化:将最大的两个数分别加入两个新数组。
过程:1.取出原数组中剩余数中的最大数,加入数组和较小的数组,若此时较小数组变
成较大数组,重复1操作,若此时较小数组依然是较小数组,执行操作2。
2.取原数组剩余数中的最小数加入较大数组。
如此直到原数组为空。 |