Lecture 16
Greedy algorithms
Knapsack Problem
Given: 1) A set of items, each with a weight and a
value.
2) Capacity/weight of Knapsack.
Goal: Determine a subset of items to include in a
collection so that the total weight is less than or equal to
a given limit and the total value is as large as possible.
2
Greedy approach to Knapsack
Problem
First • Sort in non-increasing order of
values.
approach
Second • Sort the objects based on
increasing weight values.
approach
Third • Sort the objects based on
decreasing Profit/weight values.
approach
3
First Greedy approach
4
Second Greedy approach
5
Third Greedy approach
6
Comparison of profits
Approach Description Profit value
obtained
First Greedy for Profits 28.2
Second Greedy for Weights 31
Third Greedy for Profit/Weights 31.5
Maximum
Profit
7
Fractional Knapsack algorithm
Fractional Knapsack (Array W, Array V, int M)
for i 1 to size (V)
calculate cost[i] V[i] / W[i]
Sort-Descending (cost)
i←1
while (i <= size(V))
if W[i] <= M
M ← M – W[i]
total ← total + V[i];
if W[i] > M
i ← i+1
8
Complexity Analysis
• The main time taking step is the sorting of all items in
the decreasing order of their value / weight ratios.
If using a simple sort algorithm (selection, bubble…) then the
complexity of the whole problem is O(n2).
If using quick sort or merge sort then the complexity of the
whole problem is O(nlogn).
• If the items are already arranged in the required
order, the while loop takes O(n) time.
9
In Class Practice
Q. For the given set of items and knapsack capacity = 60
kg, find the optimal solution for the fractional knapsack
problem making use of greedy approach.
10
Solution
Step 1: Compute the value / weight ratio for each item-
11
Step 2: Sort all the items in the decreasing order of their
value / weight ratios-
Step 3: Start filling the knapsack by putting the items in
it one by one.
12
• Knapsack weight left to be filled is 20 kg but item-4 has a weight of 22
kg.
• But because in fractional knapsack problem, we can even take the
fraction of any item.
• So, our knapsack will contain the items-
[ I1 , I2 , I5 , (20/22) I4 ]
Total Profit = = 160 + (20/27) x 77 = 230 Units
13
Quiz Questions
1. What is the objective of the knapsack problem?
a) To get maximum total value in the knapsack
b) To get minimum total value in the knapsack
c) To get maximum weight in the knapsack
d) To get minimum weight in the knapsack
[Link] knapsack problem can be solved in time
O(n).
a) True 14
Quiz Questions
3. Time complexity of fractional knapsack problem is ____________
a) O(n log n)
b) O(n)
c) O(n2)
d) O(nW)
[Link] items as {value,weight} pairs {{40,20},{30,10},{20,5}}. The
capacity of knapsack=20. Find the maximum value output assuming items
to be divisible.
a) 60
b) 80
c) 100
d) 40
15
Quiz Questions
5. The main time taking step in fractional knapsack problem is
___________
a) Breaking items into fraction
b) Adding items into knapsack
c) Sorting
d) Looping through sorted items
6. In Greedy method we get ________ Feasible solutions.
a) one
b) more than one
c) zero
d) hundred
16
Solutions
1. a)
2. a)
3. a)
4. a)
Explanation: The value/weight ratio are-{2,3,4}. So we include
the second and third items wholly into the knapsack. This
leaves only 5 units of volume for the first item. So we include
the first item partially. Final value = 20+30+(40/4)=60.
5. c)
6. a)
17