資料結構與演算法

(10 points) Consider the following decision problem ODDNUMBERSUM.

ODDNUMBERSUMInput: A set of positive odd numbers $S$. A target odd number $k$. Question: Is there an odd number of elements in $S$ whose sum is exactly $k$?

(a) (5 points) Prove that ODDNUMBERSUM is NP-complete.

(b) (5 points) For any set of numbers $T$ we define $\mathrm{sum}(T)$ to be the sum of all numbers in $T$. Let $S$ and $k$ be the input from ODDNUMBERSUM. Define $k^* = \max\{\mathrm{sum}(T) \mid T \subseteq S \text{ and } \mathrm{sum}(T) \le k\}$ to be the largest possible subset sum among all subsets whose sum does not exceed $k$.

Let $\varepsilon > 0$ be any sufficiently small constant. Give an algorithm that computes an $(1-\varepsilon)$-approximate solution to $k^*$. Specifically, your algorithm should output a value $k_{\mathrm{ALG}}$ such that $(1-\varepsilon)k^* \le k_{\mathrm{ALG}} \le k^*$. The running time of your algorithm should be a polynomial of $|S|$ and $1/\varepsilon$. State the algorithm as concisely and precisely as possible. You should not write anything besides the algorithm.