b******7 发帖数: 79 | 1 最近提了几个题,大家都特别支持,非常感谢!!
Given N signed integers A[1,...,N], find N correct signs S[1,..,N] (S[i] = 1
or -1), such that F[N] = A[1]*S[1] + A[2]*S[2] + ... + A[N}*S[N] = 0,
assuming we knew that such a solution must exist.
这道题我想了很久也不会。感觉上使用DP. 但是找不出比较巧的方法来表示
subproblems.
F[N] = 0, 则|F[N-1]| = |S[N]|, 然后每个subproblem A[i] 不过有2个值,应该能
有很巧的方法表示这个。请各位大虾赐教啊! |
b***e 发帖数: 1419 | 2 No solution to this one, you can pretty much give up.
Google:
- Partition problem
- NP hard
- NP completeness |
g*******y 发帖数: 1930 | 3 yes, it's NPC
set partition
正号和符号其实就是对数组的一个partition,F等于0,就是要求partition的两个subset相等。这不就是NPC了嘛。
可以用knapsack类似的DP,或者用backtracking的方法做。
1
【在 b******7 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 最近提了几个题,大家都特别支持,非常感谢!! : Given N signed integers A[1,...,N], find N correct signs S[1,..,N] (S[i] = 1 : or -1), such that F[N] = A[1]*S[1] + A[2]*S[2] + ... + A[N}*S[N] = 0, : assuming we knew that such a solution must exist. : 这道题我想了很久也不会。感觉上使用DP. 但是找不出比较巧的方法来表示 : subproblems. : F[N] = 0, 则|F[N-1]| = |S[N]|, 然后每个subproblem A[i] 不过有2个值,应该能 : 有很巧的方法表示这个。请各位大虾赐教啊!
|
r****o 发帖数: 1950 | 4 大虾能不能详细说说怎么用DP做啊?
subset相等。这不就是NPC了嘛。
【在 g*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : yes, it's NPC : set partition : 正号和符号其实就是对数组的一个partition,F等于0,就是要求partition的两个subset相等。这不就是NPC了嘛。 : 可以用knapsack类似的DP,或者用backtracking的方法做。 : : 1
|
g*******y 发帖数: 1930 | 5 就是跟knapsack类似的方法啊。
伪多项式算法。
bool state[i][j] = whether you can find a subset from A[1...i] that sums to
j;
i<=N;
j<=Total_Sum/2
state[i][j] = state[i-1][j-A[i]] || state[i-1][j]
【在 r****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 大虾能不能详细说说怎么用DP做啊? : : subset相等。这不就是NPC了嘛。
|
r****o 发帖数: 1950 | 6
to
多谢,请问
为什么要用state[i-1][j]? 这里第[i]项是必须取的把?
另外,是不是也要考虑state[i-1][j+A[i]]? 因为A[i]可取正负?
【在 g*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 就是跟knapsack类似的方法啊。 : 伪多项式算法。 : bool state[i][j] = whether you can find a subset from A[1...i] that sums to : j; : i<=N; : j<=Total_Sum/2 : state[i][j] = state[i-1][j-A[i]] || state[i-1][j]
|
g*******y 发帖数: 1930 | 7
你从1..i个元素中选一个子集,当然i可选可不选了。
我忘了说,把A数组的数先全部取绝对值变成正数。
【在 r****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : to : 多谢,请问 : 为什么要用state[i-1][j]? 这里第[i]项是必须取的把? : 另外,是不是也要考虑state[i-1][j+A[i]]? 因为A[i]可取正负?
|
r****o 发帖数: 1950 | 8 貌似这道题所有的元素都得选阿,要么正号要么负号。
另外,为什么把所有的值都取正呢?
【在 g*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 你从1..i个元素中选一个子集,当然i可选可不选了。 : 我忘了说,把A数组的数先全部取绝对值变成正数。
|
g*******y 发帖数: 1930 | 9 我说的方法是做set partition的
而这题是跟set partition等价的。
F[N]=正数+正数+...正数 + 负数 + 负数 +...+负数 = 0
那么 正数 + 正数 + ...+正数 = abs(负数)+abs(负数)+...abs(负数)
考虑一个数组A'[], A'[i] = abs(A[i])
于是这个问题就是一个关于A'数组的set partition问题。
【在 r****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 貌似这道题所有的元素都得选阿,要么正号要么负号。 : 另外,为什么把所有的值都取正呢?
|