Answer to Question #187150 in Algorithms for tejaswini

Question

The general greedy method for the Knapsack problem first sorts the objects by some rule, and then puts the items into the knapsack according to this order subject to the capacity constraint. Consider the following three ordering rules: (a) Sort by size in increasing order. (b) Sort by profit in decreasing order. (c) Sort by profit/size in decreasing order. For each of the three above rules, give an instance to show that the approximation ratio of the greedy method using such rule can be arbitrarily large. 

Answer 1

As per the required condition in the question,

a) Sort by size in the increasing order -

Given,

N=3, objective 1 objective 2 objective 3

Weight 18 15 10

Profit 25 24 15

Capacity of the knapsack = 20

N=3, objective 1 objective 2 objective 3

Weight 18 15 10

Profit 25 24 15

Select the object which have the minimum weight

Objective Profit Free space in knapsack

3 15 10

2 10*24/15 0

Total profit = 31

Sort by profit in decreasing order -

M = 20, objective 1 objective 2 objective 3

Weight 18 15 10

Profit 25 24 15

Objects are already sorted in decreasing order of profit.

Objective Profit Free space in knapsack

3 15 10

2 2*24/15 0

Total profit = 28.2