boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - divide array into two, sum of difference is min in O(N)
相关主题
Amazon 面试题
请教一个题目
问个面试题
merge k个数组怎样的方法好?
问个微软面试题
求教 合并两数组 并排除重复
问一个merge k sorted array的问题
请问两道题
find sum of three number in array
彭博 面试题
相关话题的讨论汇总
话题: divide话题: sum话题: array话题: difference话题: two
进入JobHunting版参与讨论
1 (共1页)
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
3
dp吧。
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.取原数组剩余数中的最小数加入较大数组。
如此直到原数组为空。
1 (共1页)
进入JobHunting版参与讨论
相关主题
彭博 面试题
问个算法题
再问一道数组题
跟人聊了一道题,怎么做最优。
amazon问题求教
请教一道题目
问G家一题
问几道算法题
优步面试,哎。。。
Google电话面试题目
相关话题的讨论汇总
话题: divide话题: sum话题: array话题: difference话题: two