Define the problem PARTITION as follows: PARTITION Input: A collection of integers. Output: YES if the collection
Question:
Define the problem PARTITION as follows:
PARTITION
Input: A collection of integers.
Output: YES if the collection can be split into two such that the sum of the integers in each partition sums to the same amount. NO otherwise.
(a) Assuming that PARTITION is \(\mathcal{N} \mathcal{P}\)-complete, prove that BIN PACKING is \(\mathcal{N} \mathcal{P}\)-complete.
(b) Assuming that PARTITION is \(\mathcal{N} \mathcal{P}\)-complete, prove that KNAPSACK is \(\mathcal{N} \mathcal{P}\)-complete.
Fantastic news! We've Found the answer you've been seeking!
Step by Step Answer:
Related Book For
Practical Introduction To Data Structures And Algorithm Analysis Java Edition
ISBN: 9780136609117
1st Edition
Authors: Clifford A. Shaffer
Question Posted: