i********r 发帖数: 12113 | 1 一个unsorted数组包含n个int值, 需要分成m段(m
中最大值最小. 能否找到mlog(n)
的算法? |
t**e 发帖数: 208 | 2 Is this the same as divide n elements into m group such that the group
average == the overall average?
If this is the case, then you can use DP. |
g*******y 发帖数: 1930 | 3 mlogn也未免太科幻了吧?
假设m=2,试试log(n)做出来?
或者又是我题意没理解对?
【在 i********r 的大作中提到】 : 一个unsorted数组包含n个int值, 需要分成m段(m: 中最大值最小. 能否找到mlog(n) : 的算法?
|
a**********s 发帖数: 588 | 4 Consider if this is possible in O(m*lg(n)):
Given a sequence of n numbers, and we know that their sum is mS. Pick a
subset of them such that their sum is S? |
i********r 发帖数: 12113 | 5 说得是. 那还能找到比O(mn)优的么?
【在 g*******y 的大作中提到】 : mlogn也未免太科幻了吧? : 假设m=2,试试log(n)做出来? : 或者又是我题意没理解对?
|
g*******y 发帖数: 1930 | 6 你能说说你的O(mn)方法么?
【在 i********r 的大作中提到】 : 说得是. 那还能找到比O(mn)优的么?
|
k*k 发帖数: 49 | 7 把 N elements 分到 M 个 区。。
有
((M-1) + N)! |
g*******y 发帖数: 1930 | 8 整复杂了,这是标准的DP题。
【在 k*k 的大作中提到】 : 把 N elements 分到 M 个 区。。 : 有 : ((M-1) + N)!
|
t****t 发帖数: 540 | 9 O(mn)是什么算法呀?
怎么想都觉得要先排序。
【在 i********r 的大作中提到】 : 说得是. 那还能找到比O(mn)优的么?
|
a*****r 发帖数: 55 | 10 m*n
m*log(n) is impossible. Think about m=2. |
|
|
a*****r 发帖数: 55 | 11 O(m,n) = O(m-1, n) + O(m, n-1) |
i********r 发帖数: 12113 | 12 bottom up,每次merge一个数, 使得和最小
【在 g*******y 的大作中提到】 : 你能说说你的O(mn)方法么?
|
r****o 发帖数: 1950 | 13 what does element [i][j] mean?
【在 a*****r 的大作中提到】 : O(m,n) = O(m-1, n) + O(m, n-1)
|
r****o 发帖数: 1950 | 14 每段的元素数目是否相同?
【在 i********r 的大作中提到】 : 一个unsorted数组包含n个int值, 需要分成m段(m: 中最大值最小. 能否找到mlog(n) : 的算法?
|
f*********r 发帖数: 68 | 15 这样贪心对么?
【在 i********r 的大作中提到】 : bottom up,每次merge一个数, 使得和最小
|
g*******y 发帖数: 1930 | 16 我觉得是有问题的。。。
至少我的状态方程算出来只能做到O(m*n^2),没找到优化的办法了。。。
【在 f*********r 的大作中提到】 : 这样贪心对么?
|
f*********r 发帖数: 68 | 17 这题有很多解法.
DP可以优化到O(m*n*log(n)).
还可以用二分+贪心. 复杂度在某些情况下比DP要好!
面试的话O(m*n^2)的DP应付一下足以
【在 g*******y 的大作中提到】 : 我觉得是有问题的。。。 : 至少我的状态方程算出来只能做到O(m*n^2),没找到优化的办法了。。。
|
g*******y 发帖数: 1930 | 18 你能说说你的优化是什么思路吗?
【在 f*********r 的大作中提到】 : 这题有很多解法. : DP可以优化到O(m*n*log(n)). : 还可以用二分+贪心. 复杂度在某些情况下比DP要好! : 面试的话O(m*n^2)的DP应付一下足以
|
k***e 发帖数: 556 | 19 放什么飞机?npc也搞出来了。
In computer science, the partition problem is an NP-complete problem. The
problem is to decide whether a given multiset of integers can be partitioned
into two "halves" that have the same sum. More precisely, given a multiset
S of integers, is there a way to partition S into two subsets S1 and S2 such
that the sum of the numbers in S1 equals the sum of the numbers in S2?
如果可以多项式时间解决楼主的问题,只要m取2,看得到的subset summation是否等于
sum/2,就可以回答该set是否能够partition的query?
麻烦大侠以后能贴点靠谱的题目。
【在 i********r 的大作中提到】 : 一个unsorted数组包含n个int值, 需要分成m段(m: 中最大值最小. 能否找到mlog(n) : 的算法?
|
g*******y 发帖数: 1930 | 20 不是NPC,题目是分成m段(切m-1刀),不是m个subset
partitioned
multiset
such
【在 k***e 的大作中提到】 : 放什么飞机?npc也搞出来了。 : In computer science, the partition problem is an NP-complete problem. The : problem is to decide whether a given multiset of integers can be partitioned : into two "halves" that have the same sum. More precisely, given a multiset : S of integers, is there a way to partition S into two subsets S1 and S2 such : that the sum of the numbers in S1 equals the sum of the numbers in S2? : 如果可以多项式时间解决楼主的问题,只要m取2,看得到的subset summation是否等于 : sum/2,就可以回答该set是否能够partition的query? : 麻烦大侠以后能贴点靠谱的题目。
|
k***e 发帖数: 556 | |
i********r 发帖数: 12113 | 22 能具体说一下怎么二分+贪心么?
【在 f*********r 的大作中提到】 : 这题有很多解法. : DP可以优化到O(m*n*log(n)). : 还可以用二分+贪心. 复杂度在某些情况下比DP要好! : 面试的话O(m*n^2)的DP应付一下足以
|