Question

In: Computer Science

Prove that the 0/1 KNAPSACK problem is NP-Hard. (One way to prove this is to prove...

Prove that the 0/1 KNAPSACK problem is NP-Hard. (One way to prove this is to prove the decision version of 0/1 KNAPSACK problem is NP-Complete. In this problem, we use PARTITION problem as the source problem.)

(a) Give the decision version of the O/1 KNAPSACK problem, and name it as DK.

(b) Show that DK is NP-complete (by reducing PARTITION problem to DK).

(c) Explain why showing DK, the decision version of the O/1 KNAPSACK problem, is NP-Complete is good enough to show that the O/1 KNAPSACK problem is NP-hard.

Solutions

Expert Solution

The following pages consists of the information showing how Knapsack problem is NP-Hard.


Related Solutions

What is NP? What is P? What is NP-complete? What is NP- hard?
What is NP? What is P? What is NP-complete? What is NP- hard? Give brief definitions. Give an example of an NP- complete problem. Is P equal to NP?
Assuming that SAT is NP-hard, prove that both SAT and 3-SAT (which is SAT restricted to...
Assuming that SAT is NP-hard, prove that both SAT and 3-SAT (which is SAT restricted to only having clauses containing at most three literals) are NP-complete.
In C++ or Java Write the Greedy programming Algorithm for the 0-1 Knapsack problem.                    (a)...
In C++ or Java Write the Greedy programming Algorithm for the 0-1 Knapsack problem.                    (a) No fraction allowed Max Weight W= 9 item 1: profit $20, weight 2, prof/weight=$10 item 2: profit $30, weight 5, prof/weight=$6 item 3: profit $35, weight 7, prof/weight=$5 item 4: profit $12, weight 3, prof/weight=$4 item 5: profit $3, weight 1, prof/weight=$3
Show that the following problem is NP-hard. Input: A boolean function in CNF such that every...
Show that the following problem is NP-hard. Input: A boolean function in CNF such that every clause has at most three literals and every variable appears in at most three clauses. Output: An assignment that evaluates the given function TRUE.
Recall the dynamic programming algorithm we saw in class for solving the 0/1 knapsack problem for...
Recall the dynamic programming algorithm we saw in class for solving the 0/1 knapsack problem for n objects with a knapsack capacity of K. In particular, we characterized our recurrence OPT(j, W) to be following quantity: OPT(j, W) := The maximum profit that can be obtained when selecting from objects 1, 2, . . . , j with a knapsack capacity of W , where (after filling in our dynamic programming table), we return the value stored at OPT(n, K)...
What are the different algorithms we may use to solve the 0/1 Knapsack problem? Compare and...
What are the different algorithms we may use to solve the 0/1 Knapsack problem? Compare and contrast the different methods.
discuss the differences and similarities (implementation and performance) between the solution for 0-1 knapsack problem using...
discuss the differences and similarities (implementation and performance) between the solution for 0-1 knapsack problem using Backtracking versus Branch and Bound. Do not just define the algorithms compare the performance and implementation of the 0-1 knapsack problem
The Knapsack problem is an optimization problem that asks to fill a knapsack with maximum possible...
The Knapsack problem is an optimization problem that asks to fill a knapsack with maximum possible value. Using greedy paradigm, we can solve this problem easily. Your task is the following: (a) Write the pseudo-code of a greedy solution for knapsack problem. (b) Give is the time complexity of your solution in part (a). (c) Implement part (a) in C programming language.
The Knapsack problem is an optimization problem that asks to fill a knapsack with maximum possible...
The Knapsack problem is an optimization problem that asks to fill a knapsack with maximum possible value. Using greedy paradigm, we can solve this problem easily. Your task is the following: (a) Write the pseudo-code of a greedy solution for knapsack problem. (b) Give is the time complexity of your solution in part (a). (c) Implement part (a) in C programming language.
What is P-Problem? What is NP-Problem? What is NP-Complete problem?
What is P-Problem? What is NP-Problem? What is NP-Complete problem?
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT