7 数值问题

7.1 子集和问题

【子集和问题】
给定自然数w_1,w_2,…,w_n和目标值W,问{w_1,w_2,…,w_n}有一个子集加起来恰好等于W吗?
Ex: { 1, 4, 16, 64, 256, 1040, 1041, 1093, 1284, 1344 }, W = 3754.
Yes. 1 + 16 + 64 + 256 + 1040 + 1093 + 1284 = 3754.

7.2 子集和问题是NP完全的

首先证明子集和问题是NP的。给定自然数和目标W,直接求子集中元素的合,判断是否等于W。因此可以在多项式时间内验证答案是否正确。
可以通过证明三维匹配\leq_p子集和,证明子集和问题是一个NPC问题。
【三维匹配 \leq_p 子集和】
对于三维匹配的T中的每一个元素t_a=(x_i,y_j,z_k),新建一个3n(n为自然数的个数)位的d进制串(d=m+1),3n位对应X、Y、Z的3n个元素。置第i位,第n+j位,第2n+k位为1,其他位为0。用10进制表示,则w_n=d_{i-1}+d_{n+j-1}+d_{2n+k-1}。因此W={w_1,w_2,…,w_n}。取d进制是为了防止进位。
于是,可以设k=A=\sum_{i=0}^{3n-1}d_{i}
归约完成。可以证明有一个完美的三维匹配当且仅当子集和问题中子集存在。
证明:假设有一个完美三维匹配T={t_1′,t_2′,…,t_n’},T的大小为n。在T中的每一个元素t_i都在W’中对应一个元素w_{t_i}。因为在三维匹配中所有的元素只出现一次,因此W中的所有元素相加得到一个3n位全为1的串,则\sum_{w \in W’}w=A
同时,假设有一个子集W’ \subseteq W,使得\sum_{w \in W’}w=A。对于任意的元素w \in W’,转换为d进制后都有3个位为1,对应于T的某一个元素。这些元素构成集合T,T中恰好包含X、Y、Z每个元素一次,因此T是一个完美匹配。

0
Posted in 算法设计与分析

Leave a Comment:

电子邮件地址不会被公开。