CODEWITHSUNDEEP
algorithmknapsack-problem
user1311286
user1311286

Reputation:

Fractional Knapsack + "yields a solution that is less than 1% of optimal for the 0/1 Knapsack."

I am going over a review for an upcoming test and was wondering if someone could restate part b of the question. This is the text from the review sheet passed out, but I am not sure what part b is asking exactly. I guess more straitly what does it mean by "yields a solution that is less than 1% of optimal for the 0/1 Knapsack problem."

a) Solve the following instance of the Knapsack problem, i.e., give fraction of each object chosen and value of optimal Knapsack. Show steps:

Capacity of Knapsack is C = 100

** Here he lists the objects, their values, and weights. in a table **

b) [10pts] Give an example with two objects that shows that the same greedy method used for the fractional Knapsack problem (slightly modified to leave out the last object chosen by the greedy method if it doesn’t fit) yields a solution that is less than 1% of optimal for the 0/1 Knapsack problem.

Upvotes: 0

Views: 1262

Answers (3)

anonymous
anonymous

Reputation: 201

I understand the part b) demanding to show that the greedy algorithm in not optimal and furthermore can yield less than 1% of the optimal value. This is the case already with small instances. Consider the following instance:

Item 1: profit 2, weight 1 (efficiency is 2/1 = 200/100 = 2)
Item 2: profit 400, weight 400 (efficiency is 400/400 = 1)

Knapsack capacity: 400

Note that the items are given in non-increasing order of efficiency, which is the order in which the greedy algorithm processes them. Now the greedy algorithm would chose item 1 since it fits, but now item 2 cannot be chosen. This yields a profit of 2. However, choice of item 2 yields a profit of 400. In total, the greedy algorithm yields a profit of 2 where the optimal value is at least 400, hence the greedy algorithm yields less than 1 percent of the optimal profit.

Upvotes: 0

j_random_hacker
j_random_hacker

Reputation: 51316

Usually the greedy heuristic works pretty well for the knapsack problem. If you just come up with a small problem instance at random, it's likely that applying the greedy heuristic will produce a good, or possibly even optimal solution. (The quality of a solution is measured by taking the total value of the objects it includes, and computing the ratio of that to the total value of the objects included in an optimal solution.)

This question is asking you to come up with a nasty problem instance (i.e. a list of objects with values and weights) that confuses the greedy heuristic so much that applying it yields a knapsack containing only 1% of the value that an optimal solution would contain.

Upvotes: 1

Debobroto Das
Debobroto Das

Reputation: 862

The Knapsack problem belongs to NP. I think second parts asks for a polynomial time approximation algorithm based on a greedy strategy(where the optimal solution is of exponential time complexity) which gives a solution which differs from the optimal solution by just 1%.

for example if the optimal answer is 100, the approximation algo should give a result of 99 or 101.

Upvotes: -1

Related Questions