Problem P:
Let C be a natural integer set {c1, c2 .. cn}
given a function e(x), try to partition C in to some groups G1, G2 .. Gm
such that Σe(Gi) is minimal, where e(Gi) = e(Σ(c in Gi)),
answer is the minimal value of Σe(Gi).
P can be reduced to a partition problem:
Let H =Σci/2, set e(H) = 0 and e(x) = 1 for all x != H
then P's answer is 0 iff C can be divided into two
parts and the sum of each part are equal.
Since the partition problem is NPC, so is P
--
It's the state of bliss you think you're dreaming
It's the happiness inside that you're feeling
It's so beautiful it makes you wanna cry
It's so beautiful it makes you want to cry
--
※ 發信站: 批踢踢兔(ptt2.cc)
◆ From: 140.112.3.52