c**c 发帖数: 74 | 1 面试题,感觉是下面believeme 的升级版。
give a polynomial complexity algorithm to find whether a set of intergers
can be evenly divided into 3 subsets. that is: if sum of the set is A,
decide whether it can be divided into 3 subsets, each with sum = A/3.
大意是,
两组整数A,B,没有排序, 长度分别为m,n,A中数是体积,B中数是容积大小
比如将A,B排序后,得到 比如 A= {17,16,16,13,12,7,4,3,2,1}
B={27,23,19,17,4,2,1}
A 中有17,4,3,1, B有27。那么,
27=17
27=17+4+3
27=17+4+3+1
把A中的数往B中放, 有什么方法能让放入B的数尽可能balance, A中的数如果放不到B
中可以不放。
有什么解法?
NP-complete,又近似的优化解法吗 |
c**c 发帖数: 74 | |
f*****e 发帖数: 2992 | 3 往前面搜han6的文章。
【在 c**c 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 面试题,感觉是下面believeme 的升级版。 : give a polynomial complexity algorithm to find whether a set of intergers : can be evenly divided into 3 subsets. that is: if sum of the set is A, : decide whether it can be divided into 3 subsets, each with sum = A/3. : 大意是, : 两组整数A,B,没有排序, 长度分别为m,n,A中数是体积,B中数是容积大小 : 比如将A,B排序后,得到 比如 A= {17,16,16,13,12,7,4,3,2,1} : B={27,23,19,17,4,2,1} : A 中有17,4,3,1, B有27。那么, : 27=17
|
c**c 发帖数: 74 | 4 考古了han6的文章,楼主是说最多装满水的桶得吗?
http://www.mitbbs.com/article_t/JobHunting/32136993.html
感觉那个target是将桶尽量装满,不是最不balance的吗?如何得到最balance的呢? |
d**********x 发帖数: 4083 | 5 什么叫做balance,你总得给个评估函数。
方差最小?
【在 c**c 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 考古了han6的文章,楼主是说最多装满水的桶得吗? : http://www.mitbbs.com/article_t/JobHunting/32136993.html : 感觉那个target是将桶尽量装满,不是最不balance的吗?如何得到最balance的呢?
|
b*****u 发帖数: 648 | 6 我觉得这个可以用DP 像 leetcode 的combination sum 一样
相当于找零钱的问题 |
c**c 发帖数: 74 | 7 是的
【在 d**********x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 什么叫做balance,你总得给个评估函数。 : 方差最小?
|