b*******e
发帖数: 217 | 1 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. | p*****2
发帖数: 21240 | | f*****e
发帖数: 2992 | 3 2D dp
【在 b*******e 的大作中提到】
: 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.
| b*******e
发帖数: 217 | 4 more details? I can only think of dynamical programming with n * A^3.
【在 p*****2 的大作中提到】
: DFS
| p*****2
发帖数: 21240 | 5
give a polynomial complexity algorithm
【在 f*****e 的大作中提到】
: 2D dp
| b*******e
发帖数: 217 | 6 more details? I can only think a 4-D DP (i, a1, a2, a3)
【在 f*****e 的大作中提到】
: 2D dp
| p*****2
发帖数: 21240 | 7
DFS先找到1/3， 再继续找下一个1/3
【在 b*******e 的大作中提到】
: more details? I can only think a 4-D DP (i, a1, a2, a3)
| b*******e
发帖数: 217 | 8 how to find the first 1/3?
【在 p*****2 的大作中提到】
:
: DFS先找到1/3， 再继续找下一个1/3
| f*****e
发帖数: 2992 | 9 以前讨论过的,tninja给的一个答案。
【在 p*****2 的大作中提到】
:
: DFS先找到1/3， 再继续找下一个1/3
| p*****2
发帖数: 21240 | 10
不好意思。是我理解错了。那就DP吧。
【在 f*****e 的大作中提到】
: 以前讨论过的,tninja给的一个答案。
| | | f*****e
发帖数: 2992 | | r*********n
发帖数: 4553 | 12 类似http://people.csail.mit.edu/bdean/6.046/dp/ 里面的第7题balanced partition
假设A是3的倍数，n是数列长度
vector DP[0,1,...,A][0,1,...,n-1]
every time you consider a new integer, fill in one column of DP，the
difference between this problem and the balanced partition problem is that
DP[s][i] is now a vector contains all indices leading to subset sum being
equal to s。
when you back track starting at DP[A/3][n-1], you can easily get all
feasible subsets. Then it's not difficult to determine whether three of them
form the original array.
As such, this may lead to exponential running time when all integers are
equal. To guarantee polynomial time, for each feasible subset, you repeat
the above procedure for the remaining integers that are not in this set. | h***i
发帖数: 1970 | 13 最多pseudo polynomial，用DP。本身是一个sum of subset问题，NP complete.
【在 b*******e 的大作中提到】
: 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.
| p*****2
发帖数: 21240 | 14
them
感觉写起代码来也不容易呀。
【在 r*********n 的大作中提到】
: 类似http://people.csail.mit.edu/bdean/6.046/dp/ 里面的第7题balanced partition
: 假设A是3的倍数，n是数列长度
: vector DP[0,1,...,A][0,1,...,n-1]
: every time you consider a new integer, fill in one column of DP，the
: difference between this problem and the balanced partition problem is that
: DP[s][i] is now a vector contains all indices leading to subset sum being
: equal to s。
: when you back track starting at DP[A/3][n-1], you can easily get all
: feasible subsets. Then it's not difficult to determine whether three of them
: form the original array.
| b*****u
发帖数: 648 | 15 恩，感觉就是leetcode上combination sum的升级版 | b*******e
发帖数: 217 | 16 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? | j********x
发帖数: 2330 | 17 方便透露一下哪家公司的题目么
这题如果不是考察算法基础知识，只能说面试官有意刁难
不要说找到三个，就是找到一个subset sum == A/3都是npc。。。
【在 b*******e 的大作中提到】
: 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.
|
|
