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.

venereology answered 1 year ago

Next > < Previous

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.

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?

Prove that the partition problem is NP-complete by giving a polynomial time reduction of the subset-sum...

Prove that the partition problem is NP-complete by giving a polynomial time reduction of the subset-sum problem to the partition problem.

Knapsack algorithm problem: Consider the following variation of the Knapsack problem. There are n types of...

Knapsack algorithm problem: Consider the following variation of the Knapsack problem. There are n types of items, let call them 1,2,3,4,...,n. There are exactly c_i copies of item i, and each such copy has value v_i and weight w_i. As before, the knapsack capacity is W, and the other constraint is that you can only take at most c_i copies of item i ( since no more are available). Show how to compute the optimal value that can be achieved...

Subjects