CODEWITHSUNDEEP
runtimetime-complexityknapsack-problemnp
Jeahinator
Jeahinator

Reputation: 77

Real Weights Knapsack in polynomialtime

In the lecture, we have considered the Knapsack problem: There are n items with positive weights w1, . . . , wn and values v1, . . . , vn and a knapsack (a bag) of capacity W. A feasible solution to the problem is a subset of the items such that their total weight does not exceed W. The objective is to find a feasible solution of maximum possible total value. For the case where all weights are positive integers, we have discussed a dynamic programming solution that solves the knapsack problem in time O(nW).

a)Assume that instead of the weights, the values of all items are positive integers. The weights of the items can be arbitrary positive real numbers. Describe a dynamic programming algorithm that solves the knapsack problem if all values are positive integers.

Idea - Round the values but this would just be a approximation right? This does only work if we have limited limited decimal space...

is there an other approach?

Im even more confused of the next questions:

b) What is the running time of your algorithm? Justify your answer.

c) Knapsack is one of Karp’s NP-complete problems. Both dynamic programming solutions lead to polynomial time algorithms. Why is this not a contradiction to the NP-completeness of Knapsack?

Upvotes: 0

Views: 1336

Answers (2)

AAArAAA
AAArAAA

Reputation: 11

(a) Since values are integers and weights are real we make a table based on the values. To be more precise, lets fix an arbitrary order of items $i_1, \dots, i_n$. Define DP(i, v) be the smallest weight among subsets of items from 1 to i where value of each subset is at least v. The value of a subset is defined simply as sum of all items in that subset. Then $DP(i+1, v)=min(DP(i, v - v_{i+1}) + w_{i+1}, DP(i, v))$.

DP(i, v) can be computed for all $i=1, \dots, n$ and $v=1, \dots, V^*$, the optimum value of the problem which is bounded by $\sum_{i=1}^n v_i$. After we fill up the table, i.e. computing DP(v,i)'s we can scan and look for the entry with maximum v such that DP(i, v) is less than or equal to W, i.e. the capacity of the bag.

(b) Running time is $O(nV^*)$ which upper bounded by $O(n \sum_{i=1}^n v_i)$

(c) It won't contradict with the fact that Knapsack is NP-hard because the above algorithm and algorithm that you describe in the question are pseudo polynomial, i.e. they depend on the magnitude of vi or wi not their logs which are their actual size represented in computer memory!

Upvotes: 1

Julianne
Julianne

Reputation: 61

Part A: Since the values of all items are positive integers, and therefore the items cannot be broken meaning the items have to be taken as a whole or left behind, this is an example of the 0/1 Knapsack problem. This problem lacks the Greedy Choice Property and so cannot be solved by a Greedy approach. Dynamic Programming is necessary.

Say for example we have item 1 (total value: $60, weight: 10lbs, value/weight: $6/lb), item 2 (total value: $100, weight: 20lbs, value/weight: $5/lb), and item 3: (total value: $120, weight: 30lbs, value/weight: $4/lb).

With a greedy approach you take the most valuable item first. item 1+item 2=$160. This is not the optimal solution since if we include item 1, other items might be forced out and empty space could remain. Must look at the solution with item 1 vs. solution without item 1. This is called overlapping subproblems.

For an optimal solution, either our last item n is in the optimal solution A, or it is not.

  • If it is: The rest of the objects in the optimal solution can be found by finding optimal solution given N-{n} items and max capacity of C-s{sub n}.
  • If it is not: The rest of the objects in the optimal solution can be found by finding optimal solution given N-{n} items and max capacity of C.

To find max value(N,C): - if s{sub n} <= C: max(value(N-{n},C),v{sub n} + value(N-{n},C-s{sub n})) - if s{sub n} > C: value(N-{n},C)

As this is a lot of subproblems to try, create a table with #columns = size of backpack + 1 (i.e. 0...C, with C being size of backpack), and #rows = inputs in any order. Fill out the table with the rules listed above starting at C=0 and going across the table for each item. Choose the combination that provides the highest capacity and highest total worth.

Part B: The running time of the algorithm is O((Cn)^2). The table is Capacity x number of items. Each element in the table compares 2 values (max of not including element n{sub k}, and including element n{sub k}).

Part C: The 0/1 Knapsack is NP-complete and is polynomial in the capacity of the backpack. This is not a contradiction to the NP-completeness of the Knapsack problem because there are many instances where the capacity is O(2^n).

Upvotes: 2

Related Questions