b*7
2 楼
最近提了几个题，大家都特别支持,非常感谢！！
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个值，应该能
有很巧的方法表示这个。请各位大虾赐教啊！
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个值，应该能
有很巧的方法表示这个。请各位大虾赐教啊！
n*3
3 楼
Immunol Rev. 1995 Jun;145:5-31.
Liposomes as carriers of peptide antigens: induction of antibodies and
cytotoxic T lymphocytes to conjugated and unconjugated peptides.
Alving CR, Koulchin V, Glenn GM, Rao M.
please send the paper to e********[email protected]
Liposomes as carriers of peptide antigens: induction of antibodies and
cytotoxic T lymphocytes to conjugated and unconjugated peptides.
Alving CR, Koulchin V, Glenn GM, Rao M.
please send the paper to e********[email protected]
a*y
4 楼
可以
等着修改意见回来了再改也行
等着修改意见回来了再改也行
b*e
5 楼
No solution to this one, you can pretty much give up.
Google:
- Partition problem
- NP hard
- NP completeness
Google:
- Partition problem
- NP hard
- NP completeness
a*l
6 楼
g*y
7 楼
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个值，应该能
: 有很巧的方法表示这个。请各位大虾赐教啊！
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
8 楼
大虾能不能详细说说怎么用DP做啊？
subset相等。这不就是NPC了嘛。
【在 g*******y 的大作中提到】
: yes, it's NPC
: set partition
: 正号和符号其实就是对数组的一个partition，F等于0，就是要求partition的两个subset相等。这不就是NPC了嘛。
: 可以用knapsack类似的DP，或者用backtracking的方法做。
:
: 1
subset相等。这不就是NPC了嘛。
【在 g*******y 的大作中提到】
: yes, it's NPC
: set partition
: 正号和符号其实就是对数组的一个partition，F等于0，就是要求partition的两个subset相等。这不就是NPC了嘛。
: 可以用knapsack类似的DP，或者用backtracking的方法做。
:
: 1
g*y
9 楼
就是跟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了嘛。
伪多项式算法。
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
10 楼
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
11 楼
你从1..i个元素中选一个子集，当然i可选可不选了。
我忘了说，把A数组的数先全部取绝对值变成正数。
【在 r****o 的大作中提到】
:
: to
: 多谢，请问
: 为什么要用state[i-1][j]? 这里第[i]项是必须取的把?
: 另外，是不是也要考虑state[i-1][j+A[i]]? 因为A[i]可取正负?
r*o
12 楼
貌似这道题所有的元素都得选阿，要么正号要么负号。
另外，为什么把所有的值都取正呢？
【在 g*******y 的大作中提到】
:
: 你从1..i个元素中选一个子集，当然i可选可不选了。
: 我忘了说，把A数组的数先全部取绝对值变成正数。
另外，为什么把所有的值都取正呢？
【在 g*******y 的大作中提到】
:
: 你从1..i个元素中选一个子集，当然i可选可不选了。
: 我忘了说，把A数组的数先全部取绝对值变成正数。
g*y
13 楼
我说的方法是做set partition的
而这题是跟set partition等价的。
F[N]=正数+正数+...正数 + 负数 + 负数 +...+负数 = 0
那么 正数 + 正数 + ...+正数 = abs(负数）+abs（负数)+...abs(负数)
考虑一个数组A'[], A'[i] = abs(A[i])
于是这个问题就是一个关于A'数组的set partition问题。
【在 r****o 的大作中提到】
: 貌似这道题所有的元素都得选阿，要么正号要么负号。
: 另外，为什么把所有的值都取正呢？
而这题是跟set partition等价的。
F[N]=正数+正数+...正数 + 负数 + 负数 +...+负数 = 0
那么 正数 + 正数 + ...+正数 = abs(负数）+abs（负数)+...abs(负数)
考虑一个数组A'[], A'[i] = abs(A[i])
于是这个问题就是一个关于A'数组的set partition问题。
【在 r****o 的大作中提到】
: 貌似这道题所有的元素都得选阿，要么正号要么负号。
: 另外，为什么把所有的值都取正呢？
相关阅读
pigskin 封 USMedEdu 在 Biology 版cell paper 被挑战了成功人士不去游山玩水外行问一个transmembrane protein的实验问题医院里的technologist怎么样？查FUNDING的网站要是真的天下大乱 怎么办？读博士选老板极为重要鲁莽新人请教杂志投稿问题JBC or Hepatology?我说生物板的各位板大建议灾区同学 (转载)怎么样找clinical相关的位置？转行法医，求建议！！大家找到新位置后多长时间离开原来的实验室 (转载)国内973课题想找一结构实验室作成员Paper Help: 1985 Science求讨论蛋白结构的网站bbsBiology is Very Easy to Get Green Card.paper help, thanks a lot