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 的大作中提到】
: 最近提了几个题，大家都特别支持,非常感谢！！
: 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 的大作中提到】
: 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 的大作中提到】
: 大虾能不能详细说说怎么用DP做啊？
:
: subset相等。这不就是NPC了嘛。
|
r****o
发帖数: 1950 | 6
to
多谢，请问
为什么要用state[i-1][j]? 这里第[i]项是必须取的把?
另外，是不是也要考虑state[i-1][j+A[i]]? 因为A[i]可取正负?
【在 g*******y 的大作中提到】
: 就是跟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 的大作中提到】
:
: to
: 多谢，请问
: 为什么要用state[i-1][j]? 这里第[i]项是必须取的把?
: 另外，是不是也要考虑state[i-1][j+A[i]]? 因为A[i]可取正负?
|
r****o
发帖数: 1950 | 8 貌似这道题所有的元素都得选阿，要么正号要么负号。
另外，为什么把所有的值都取正呢？
【在 g*******y 的大作中提到】
:
: 你从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 的大作中提到】
: 貌似这道题所有的元素都得选阿，要么正号要么负号。
: 另外，为什么把所有的值都取正呢？
|
