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 的大作中提到】
: 面试题，感觉是下面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 的大作中提到】
: 考古了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 的大作中提到】
: 什么叫做balance，你总得给个评估函数。
: 方差最小？
|
