To prove that the 0/1 KNAPSACK problem is NP-Hard, we need to show that the decision version of the problem, called DK, is NP-Complete.
The decision version of the 0/1 KNAPSACK problem, DK, can be defined as follows: Given a set of items, each with a weight and a value, and a maximum weight capacity for the knapsack, is there a subset of items whose total weight does not exceed the capacity, and whose total value is at least a given threshold value?
To show that DK is NP-Complete, we can reduce the PARTITION problem to DK. The PARTITION problem is a well-known NP-Complete problem that asks whether a given set of numbers can be partitioned into two subsets with equal sums.
The reduction from PARTITION to DK involves transforming an instance of PARTITION into an instance of DK. Given an instance of PARTITION with a set of numbers, we can create an instance of DK as follows: For each number in the PARTITION instance, create an item in the DK instance with weight and value equal to the number. Set the maximum weight capacity for the knapsack in the DK instance to half of the sum of all the numbers in the PARTITION instance. Finally, set the threshold value in the DK instance to half of the sum of all the numbers in the PARTITION instance.
Now, if there exists a partition of the numbers in the PARTITION instance into two subsets with equal sums, then there exists a subset of items in the DK instance whose total weight does not exceed the capacity and whose total value is at least the threshold value. Conversely, if there exists a subset of items in the DK instance with these properties, then there exists a partition of the numbers in the PARTITION instance into two subsets with equal sums.
This reduction shows that if we can solve DK in polynomial time, then we can also solve PARTITION in polynomial time. Since PARTITION is known to be NP-Complete, this implies that DK is also NP-Complete.
(c) Showing that DK, the decision version of the 0/1 KNAPSACK problem, is NP-Complete is sufficient to prove that the 0/1 KNAPSACK problem is NP-Hard. This is because any problem that can be reduced to an NP-Complete problem is also NP-Hard. Since we have reduced the PARTITION problem to DK, which is an NP-Complete problem, it follows that the 0/1 KNAPSACK problem is NP-Hard.
In conclusion, the 0/1 KNAPSACK problem is proven to be NP-Hard by showing that its decision version, DK, is NP-Complete through a reduction from the PARTITION problem.
Learn more about 0/1 KNAPSACK problem at