d****r
发帖数: 80 | 1 一道面试题：
给定一个整数数组。怎样能将其分为三组（不要求个数相等），使每组值的总和相等。
不能分的时候返回空值。能分的时候给出一个解就行。
我只能想到三进制，有没有更优化的方法？ | c********t
发帖数: 5706 | 2 是整数吧？要求每组的整数个数相等吗？
【在 d****r 的大作中提到】
: 一道面试题：
: 给定一个整数数组。怎样能将其分为三组（不要求个数相等），使每组值的总和相等。
: 不能分的时候返回空值。能分的时候给出一个解就行。
: 我只能想到三进制，有没有更优化的方法？
| d****r
发帖数: 80 | 3 对，整数。有何高见？
【在 c********t 的大作中提到】
: 是整数吧？要求每组的整数个数相等吗？
| j*****y
发帖数: 1071 | 4 用三进制 brute force ?
【在 d****r 的大作中提到】
: 对，整数。有何高见？
| d****r
发帖数: 80 | 5 我是那么想的。三进制达不到要求。要求优化解。
【在 j*****y 的大作中提到】
: 用三进制 brute force ?
| d****r
发帖数: 80 | 6 不要求个数相等。
【在 c********t 的大作中提到】
: 是整数吧？要求每组的整数个数相等吗？
| j*****y
发帖数: 1071 | 7 二等分数组是可以用 dp的，
三等分的话，可不可以证明：
如果可以三等分的话，如果拿出一个子集的和是 1/3的和，那么剩下的一定可以二等分？
这个可以证明是正确的话，那么就是两次 dp 了
【在 d****r 的大作中提到】
: 一道面试题：
: 给定一个整数数组。怎样能将其分为三组（不要求个数相等），使每组值的总和相等。
: 不能分的时候返回空值。能分的时候给出一个解就行。
: 我只能想到三进制，有没有更优化的方法？
| j*****y
发帖数: 1071 | 8 这个可以证明是正确的，那么就是两次 dp
第一次 dp 找出和是 1/3 的总和的子集
第二次dp 等分剩下的集合
分？
【在 j*****y 的大作中提到】
: 二等分数组是可以用 dp的，
: 三等分的话，可不可以证明：
: 如果可以三等分的话，如果拿出一个子集的和是 1/3的和，那么剩下的一定可以二等分？
: 这个可以证明是正确的话，那么就是两次 dp 了
| z*******8
发帖数: 30 | 9 我觉得这个思路挺好，有点递归的意思，不过条件有点强吧。
比如
1,2,3,
0,0,5,
0,0,7
这个数组就是不能三分的。
分？
【在 j*****y 的大作中提到】
: 二等分数组是可以用 dp的，
: 三等分的话，可不可以证明：
: 如果可以三等分的话，如果拿出一个子集的和是 1/3的和，那么剩下的一定可以二等分？
: 这个可以证明是正确的话，那么就是两次 dp 了
| j*****y
发帖数: 1071 | 10 不能三分的话两次 dp 也能 detect 出来
【在 z*******8 的大作中提到】
: 我觉得这个思路挺好，有点递归的意思，不过条件有点强吧。
: 比如
: 1,2,3,
: 0,0,5,
: 0,0,7
: 这个数组就是不能三分的。
:
: 分？
| | | c********t
发帖数: 5706 | 11 应该不是正确的。1，1,3,4,6
dp 两次也不一定可以 1,1,2,3,4,4 如果第一次拿走 1，1,3，以后将无解啊
【在 j*****y 的大作中提到】
: 这个可以证明是正确的，那么就是两次 dp
: 第一次 dp 找出和是 1/3 的总和的子集
: 第二次dp 等分剩下的集合
:
: 分？
| j*****y
发帖数: 1071 | 12 哈哈，我刚才大脑过了一遍，感觉是对的，看来是错的 :)
【在 c********t 的大作中提到】
: 应该不是正确的。1，1,3,4,6
: dp 两次也不一定可以 1,1,2,3,4,4 如果第一次拿走 1，1,3，以后将无解啊
| c********t
发帖数: 5706 | 13 用dp找出=1/3*sum 的所有解，然后对每一组都取剩下的，试试能不能用dp 2等分?
是不是太复杂了？
【在 j*****y 的大作中提到】
: 哈哈，我刚才大脑过了一遍，感觉是对的，看来是错的 :)
| j*****y
发帖数: 1071 | 14 这个所有解，感觉太复杂了：）
【在 c********t 的大作中提到】
: 用dp找出=1/3*sum 的所有解，然后对每一组都取剩下的，试试能不能用dp 2等分?
: 是不是太复杂了？
| f*****e
发帖数: 2992 | 15 一个DP就行，然后就看所有解中是否有两个不相交就行。
【在 c********t 的大作中提到】
: 用dp找出=1/3*sum 的所有解，然后对每一组都取剩下的，试试能不能用dp 2等分?
: 是不是太复杂了？
| c********t
发帖数: 5706 | 16 嗯，同意
【在 f*****e 的大作中提到】
: 一个DP就行，然后就看所有解中是否有两个不相交就行。
| d**********n
发帖数: 132 | 17 不可以，有反例
分？
【在 j*****y 的大作中提到】
: 二等分数组是可以用 dp的，
: 三等分的话，可不可以证明：
: 如果可以三等分的话，如果拿出一个子集的和是 1/3的和，那么剩下的一定可以二等分？
: 这个可以证明是正确的话，那么就是两次 dp 了
| d**********n
发帖数: 132 | 18 请大牛明示，这道题的dp是找一个解吧？用一个二维数组来储存当前element可能生成
的和
【在 f*****e 的大作中提到】
: 一个DP就行，然后就看所有解中是否有两个不相交就行。
| s********i
发帖数: 145 | 19 这道题不是经典的NP-COMPLETE的problem之一么...还解个啥？ | t****a
发帖数: 1212 | 20 我把它当二维DP做了，clojure程序和结果如下
(def divide-3-sub
(memoize
(fn [s1 s2 [x & xs]]
(cond (and (zero? s1) (zero? s2)) ['() '() (cons x xs)]
(or (< s1 0) (< s2 0) (empty? xs)) nil
:else (if-let [d1 (divide-3-sub (- s1 x) s2 xs)]
(assoc d1 0 (cons x (first d1)))
(if-let [d2 (divide-3-sub s1 (- s2 x) xs)]
(assoc d2 1 (cons x (second d2)))
(if-let [d3 (divide-3-sub s1 s2 xs)]
(assoc d3 2 (cons x (last d3)))
nil)))))))
(defn divide-3 [x]
(let [s (apply + x)
s3 (int (/ s 3))]
(if (= s (* s3 3))
(divide-3-sub s3 s3 x)
nil)))
(divide-3 (take 12 (repeat 1))) ; [(1 1 1 1) (1 1 1 1) (1 1 1 1)]
(divide-3 (range 6)) ; [(0 1 4) (2 3) (5)]
(divide-3 (range 12)) ; [(0 1 2 3 7 9) (4 8 10) (5 6 11)]
(divide-3 (take 100 (repeatedly #(rand-int 20)))) ; [(19 19 5 19 3 3 7 4 2 4
18 5 16 9 4 16 7 3 12 9 3 19 2 6 13 5 0 3 0 9 3 7 12 8 17 1 7 9 17 1 0 0 0)
(17 18 17 12 19 4 9 18 5 17 3 14 19 16 7 7 1 8 3 14 4 10 19 15 4 15 17 13 1
) (16 15 10 19 6 17 11 15 18 18 14 8 17 11 17 9 19 6 5 2 2 11 7 11 19 15 5 3
)]
这个程序的计算复杂度为O(s*s*n)，其中s为数组的总和，n为数组长度。 | | | j*****y
发帖数: 1071 | 21 能把那个 optimal structure 写一下吗？
thanks.
【在 t****a 的大作中提到】
: 我把它当二维DP做了，clojure程序和结果如下
: (def divide-3-sub
: (memoize
: (fn [s1 s2 [x & xs]]
: (cond (and (zero? s1) (zero? s2)) ['() '() (cons x xs)]
: (or (< s1 0) (< s2 0) (empty? xs)) nil
: :else (if-let [d1 (divide-3-sub (- s1 x) s2 xs)]
: (assoc d1 0 (cons x (first d1)))
: (if-let [d2 (divide-3-sub s1 (- s2 x) xs)]
: (assoc d2 1 (cons x (second d2)))
| t****a
发帖数: 1212 | 22 f(s1, s2, (x & xs)) = f(s1-x, s2, xs) or f(s1, s2-x, xs) or f(s1, s2, xs)
f(0, 0, (x & xs)) 时候成功
话说楼主的3进制是什么意思啊？ | j*****y
发帖数: 1071 | 23 s1 是第一个 subset, s2 是第二个 subset ?
x 和 xs 是什么呢？
【在 t****a 的大作中提到】
: f(s1, s2, (x & xs)) = f(s1-x, s2, xs) or f(s1, s2-x, xs) or f(s1, s2, xs)
: f(0, 0, (x & xs)) 时候成功
: 话说楼主的3进制是什么意思啊？
| t****a
发帖数: 1212 | 24 (x & xs)整体表示输入的数字序列。s1是该数字序列中需要分出来第一组的和和第二组
的和。本题s1=s2=1/3 * sum(x & xs)
【在 j*****y 的大作中提到】
: s1 是第一个 subset, s2 是第二个 subset ?
: x 和 xs 是什么呢？
| w**********o
发帖数: 140 | 25 小弟抛块砖，希望大牛们点评下。
首先sort， 从大到小排列。
L: 100, 98, 97, 76, 50, 30, ...., 10, 9, 2,1
分3组, a, b, c. 挨个拿。
First time
a: 100
b: 98
c: 97
sum(a) = 100
sum(b) = 98
sum(c) = 97 最小, 把L里面最大的分给他
Second time
a: 100,
b: 98,
c: 97, 76
sum(a) =100
sum(b) = 98 最小, 把L里面最大的分给他
sum(c) =173
3rd
a: 100,
b: 98, 50,
c: 97, 76,
sum(a) =100 最小, 把L里面最大的分给他
sum(b) = 148
sum(c) = 173
3rd
a: 100, 30
b: 98, 50,
c: 97, 76,
以此类推， 全部分完。
这样3组的difference比较小，size基本一样的情况下。
算法：个人理解就和国内分蛋糕一样。
每人都拿一块， c拿最小的要说话了， 再给我一份。
c变最大， b说他也要，一次不行，两次，拿到他是最大的（最小的变最大的）。
接着a也不服气，直到大家找到平衡点(找到组合)， 要么掀桌
子（return null）。
可用structure,： 2个heap， one min heap for 3(a,b,c), one max heap for list(
same thing as sorted list)。
====
回复楼上，估计不是测试DP问题，interviewer没那个闲工夫测试30mins吧。 | t****a
发帖数: 1212 | 26 这个会挂掉的。因为解的个数在最糟糕情况下是个组合数。
【在 f*****e 的大作中提到】
: 一个DP就行，然后就看所有解中是否有两个不相交就行。
| t****a
发帖数: 1212 | 27 这样的方法好像是贪婪，不知道能不能保证找到结果啊。我数学不好，有哪位朋友来证
明一下贪婪对不对么？
【在 w**********o 的大作中提到】
: 小弟抛块砖，希望大牛们点评下。
: 首先sort， 从大到小排列。
: L: 100, 98, 97, 76, 50, 30, ...., 10, 9, 2,1
: 分3组, a, b, c. 挨个拿。
: First time
: a: 100
: b: 98
: c: 97
: sum(a) = 100
: sum(b) = 98
| w**********o
发帖数: 140 | 28 题目本身是NP， 所以应该没问题吧。
希望PeK能点评下。
【在 t****a 的大作中提到】
: 这样的方法好像是贪婪，不知道能不能保证找到结果啊。我数学不好，有哪位朋友来证
: 明一下贪婪对不对么？
| d**********x
发帖数: 4083 | 29 http://poj.org/problem?id=1011
一个区别不大的问题，poj的这个只是组数不确定
如果没记错的话，没有多项式解法，只是暴力搜索，加上各种神奇的剪支。
【在 d****r 的大作中提到】
: 一道面试题：
: 给定一个整数数组。怎样能将其分为三组（不要求个数相等），使每组值的总和相等。
: 不能分的时候返回空值。能分的时候给出一个解就行。
: 我只能想到三进制，有没有更优化的方法？
| s********i
发帖数: 145 | 30
我都说了是NP-COMPLETE了，为什么大家都无视我呢... T_T
【在 d**********x 的大作中提到】
: http://poj.org/problem?id=1011
: 一个区别不大的问题，poj的这个只是组数不确定
: 如果没记错的话，没有多项式解法，只是暴力搜索，加上各种神奇的剪支。
| | | d**********x
发帖数: 4083 | 31 真没看见你那篇。。
【在 s********i 的大作中提到】
:
: 我都说了是NP-COMPLETE了，为什么大家都无视我呢... T_T
| f*****e
发帖数: 2992 | 32 对NP-complete，你能搞个pseudopolynoimal算法，也很nb的。
【在 s********i 的大作中提到】
:
: 我都说了是NP-COMPLETE了，为什么大家都无视我呢... T_T
| v*******e
发帖数: 326 | 33 既然是np complete 为啥还要考楼主算法和优化解?
【在 s********i 的大作中提到】
:
: 我都说了是NP-COMPLETE了，为什么大家都无视我呢... T_T
| s****r
发帖数: 28 | 34 这个不就是相当于leetcode上的combination sum么？
target = total_sum/3
如果能找两个不相交的组合就可以了
【在 d****r 的大作中提到】
: 一道面试题：
: 给定一个整数数组。怎样能将其分为三组（不要求个数相等），使每组值的总和相等。
: 不能分的时候返回空值。能分的时候给出一个解就行。
: 我只能想到三进制，有没有更优化的方法？
| d**********x
发帖数: 4083 | 35 Once I was interviewed by fb and the interviewer told me the problem IS an
NP, but he still wanted to see how optimized algorithm I could give
【在 v*******e 的大作中提到】
: 既然是np complete 为啥还要考楼主算法和优化解?
| d****r
发帖数: 80 | 36
穷举。N个数的话，用N位的三进制。从0扫到最大值。0,1,2对应三个组。我这个方法实
际上没什么用。
【在 t****a 的大作中提到】
: f(s1, s2, (x & xs)) = f(s1-x, s2, xs) or f(s1, s2-x, xs) or f(s1, s2, xs)
: f(0, 0, (x & xs)) 时候成功
: 话说楼主的3进制是什么意思啊？
| b*******e
发帖数: 217 | 37 my solution: 4d np.
recursive function.
Exist(i, a1, a2, a3) = { Exist(i-1, a1-xi, a2, a3) ||
Exist(i-1, a1, a2-xi, a3) ||
Exist(i-1, a1, a2, a3-xi) }
where xi is the ith integer.
a1, a2, a3 are the sum of three subsets in the set.
start from i = 1, a1, a2, a3 = 1
stop at i = n, a1 = a2 = a3 = sum/3.
complexity n * (sum/3)^3.
Any problem with the above DP?
【在 d****r 的大作中提到】
:
: 穷举。N个数的话，用N位的三进制。从0扫到最大值。0,1,2对应三个组。我这个方法实
: 际上没什么用。
| c********t
发帖数: 5706 | 38 两个问题
1.如何保证同一个元素没有被a1,a2,a3重用
2.a3需要吗？如果能求出a1,a2就不用a3了吧。n * (sum/3)^2.
【在 b*******e 的大作中提到】
: my solution: 4d np.
: recursive function.
: Exist(i, a1, a2, a3) = { Exist(i-1, a1-xi, a2, a3) ||
: Exist(i-1, a1, a2-xi, a3) ||
: Exist(i-1, a1, a2, a3-xi) }
: where xi is the ith integer.
: a1, a2, a3 are the sum of three subsets in the set.
: start from i = 1, a1, a2, a3 = 1
: stop at i = n, a1 = a2 = a3 = sum/3.
: complexity n * (sum/3)^3.
| f****s
发帖数: 74 | 39 背包问题也是npc啊，
【在 s********i 的大作中提到】
:
: 我都说了是NP-COMPLETE了，为什么大家都无视我呢... T_T
| c********t
发帖数: 5706 | 40 肯定是不行的
试试用你的做法把 1 3 4 5 6 7分成两组
【在 w**********o 的大作中提到】
: 小弟抛块砖，希望大牛们点评下。
: 首先sort， 从大到小排列。
: L: 100, 98, 97, 76, 50, 30, ...., 10, 9, 2,1
: 分3组, a, b, c. 挨个拿。
: First time
: a: 100
: b: 98
: c: 97
: sum(a) = 100
: sum(b) = 98
| | | b*******e
发帖数: 217 | 41 for (2): you are right.
recursive fucntion:
exist(i, a1, a2) = { exist(i-1, a1-xi, a2) ||
exist(i-1, a1, a2-xi)}
starting form i = 1 a1 = 1, a2 =1
end at i = n and a1 = a2 = sum/3.
complexity: n * (sum/3)^2.
don't quite understand (1). any example?
when start froming i = 1 to i = n, the recursive structure ... should be
able to gurantee that xi will only be used for once?
my solution: 3d np. | c********t
发帖数: 5706 | 42 for 1) example 4,6.....
exist(1,10,10)= exist(0,4,10)|| exist(0,10,4);
did ur program put 4 in a1, a2 or both? how about 6?
for 1,3,4,6,1,9, how can you prevent the result to be 1,9| 1,3,6 | 4,6 (use
6 twice)
【在 b*******e 的大作中提到】
: for (2): you are right.
: recursive fucntion:
: exist(i, a1, a2) = { exist(i-1, a1-xi, a2) ||
: exist(i-1, a1, a2-xi)}
: starting form i = 1 a1 = 1, a2 =1
: end at i = n and a1 = a2 = sum/3.
: complexity: n * (sum/3)^2.
: don't quite understand (1). any example?
: when start froming i = 1 to i = n, the recursive structure ... should be
: able to gurantee that xi will only be used for once?
| b*******e
发帖数: 217 | 43 for i == 0, only exist(0, 4, 0) and exist(0, 0, 4) = true. all other
comibinations for i == 0 including exist(0, 4, 10) = false and exist(0, 10,
4) = false, so exist(1, 10, 10) = false.
for i == 1, exist(1, 10, 0) = exist(0, 4, 0 ) || exist(0, 10, -6) = true ||
false. and exist(1, 0, 10) = exist(0, -6, 10) || exist(0, 0, 4) = false ||
true and exist(1, 4, 6) = exist(0, 4, 0) || exist(0, -2, 0) = true || false
and
exist (1, 6, 4) = exist(0, 0, 4) || exist(0, 6, -2) = true || false will be
true. All other combinations will be false.
for 1, 3, 4, 5, 1, 9, "6" participate in the selection only when i == 3. and
it will either stay with 3 and 1, or with 4 for exist(3, 10, 10).
exist(3, 10, 10) = exist(2, 4, 10) || exist(2, 10, 4) = exist(1, 0, 10) ||
exist(1, 4, 6) || exist(1, 6, .... = false.
use
【在 c********t 的大作中提到】
: for 1) example 4,6.....
: exist(1,10,10)= exist(0,4,10)|| exist(0,10,4);
: did ur program put 4 in a1, a2 or both? how about 6?
: for 1,3,4,6,1,9, how can you prevent the result to be 1,9| 1,3,6 | 4,6 (use
: 6 twice)
| c********t
发帖数: 5706 | 44 I think it will cause the problem，if continuing, later 4 might be used in
both a1 and a2.
let me simplify my second example to 6,1，3，4,10. By running ur program to
get exist(3,10,10), won't 6 be used in both a1 and a2? exist(3,[6，1,3], [6,
4])?
,
|
|
【在 b*******e 的大作中提到】
: for i == 0, only exist(0, 4, 0) and exist(0, 0, 4) = true. all other
: comibinations for i == 0 including exist(0, 4, 10) = false and exist(0, 10,
: 4) = false, so exist(1, 10, 10) = false.
: for i == 1, exist(1, 10, 0) = exist(0, 4, 0 ) || exist(0, 10, -6) = true ||
: false. and exist(1, 0, 10) = exist(0, -6, 10) || exist(0, 0, 4) = false ||
: true and exist(1, 4, 6) = exist(0, 4, 0) || exist(0, -2, 0) = true || false
: and
: exist (1, 6, 4) = exist(0, 0, 4) || exist(0, 6, -2) = true || false will be
: true. All other combinations will be false.
: for 1, 3, 4, 5, 1, 9, "6" participate in the selection only when i == 3. and
| b*******e
发帖数: 217 | 45 exist(3, 10, 10)
= exist(2, 10-4, 10) || exist(2, 10, 10-4)
= exist(2, 6, 10) || exist(2, 10, 6) = false || false = false already.
let us continue from i == 2 to i== 1
= exist(1, 3, 10) || exist(1, 6, 7) || exist(1, 7, 6) || exist(1, 6, 7)
= false || false || false || false.
we can continue from i == 1 to 0.
also we can find it is false.
So exist(3, 10, 10) = false. That indicates 6 are not used for multiple
times.
Otherwise exist(3, 10, 10) should be true.
to
6,
【在 c********t 的大作中提到】
: I think it will cause the problem，if continuing, later 4 might be used in
: both a1 and a2.
: let me simplify my second example to 6,1，3，4,10. By running ur program to
: get exist(3,10,10), won't 6 be used in both a1 and a2? exist(3,[6，1,3], [6,
: 4])?
:
: ,
: |
: |
| c********t
发帖数: 5706 | 46 好像你是对的。我有空做做看。多谢！
【在 b*******e 的大作中提到】
: exist(3, 10, 10)
: = exist(2, 10-4, 10) || exist(2, 10, 10-4)
: = exist(2, 6, 10) || exist(2, 10, 6) = false || false = false already.
: let us continue from i == 2 to i== 1
: = exist(1, 3, 10) || exist(1, 6, 7) || exist(1, 7, 6) || exist(1, 6, 7)
: = false || false || false || false.
: we can continue from i == 1 to 0.
: also we can find it is false.
: So exist(3, 10, 10) = false. That indicates 6 are not used for multiple
: times.
| b*******e
发帖数: 217 | 47 This is a problem in DP chapter of "Algorithms" by a berkeley professor. It
asked for a polynomail complexity solution whether dividing evenly by 3
exists or not.
【在 d****r 的大作中提到】
: 一道面试题：
: 给定一个整数数组。怎样能将其分为三组（不要求个数相等），使每组值的总和相等。
: 不能分的时候返回空值。能分的时候给出一个解就行。
: 我只能想到三进制，有没有更优化的方法？
|
|
