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 的大作中提到】
: 貌似这道题所有的元素都得选阿，要么正号要么负号。
: 另外，为什么把所有的值都取正呢？
相关阅读
真是烦死了去公司还是继续postdog？LC labs 这个公司的试剂靠谱吗？有人用BD Accuri C6 cytometer么有没有谁用过Li-Cor AERIUS有没有公司提供protein chip screening的服务？Paper Help代发个sanofi-aventis医学报告撰写专员Medical Writer职位（北京）码农办个培训学校会不会很赚钱？什么样的Seminar才算是好的Seminar可怜的三妹！诚聘：基因工程动物项目经理问个Y轴截断的图的做法使用bookends遇到问题，求助GraphPad PRISM,诚聘：生物 英才给前单位的领导发了一封信有人去AES开会吗，寻室友？工作快1年了，写点感想Re: 医学院已俨然成为施一公的 王国，没有异己声音，因为异己已 (转载)