Greedy Algorithm - 1 - Knapsack Problem

COMP108 Lectures 2021-04-21

The process of the greedy algorithm is explained in this lecture:

• COMP111 - Informed Strategies

The main idea is to bin pack using the largest items first.

Greedy algorithm doesn’t always find an optimal solution but it is easy to implement.

Knapsack Problem

You want to steal the best items from a house optimising for:

• Least Weight
• Most Value

Formally this can be written like so:

Given $n$ items with weights $w_1,w_2,\ldots,w_n$, values $v_1,v_2,\ldots,v_n$ and a knapsack with capacity $W$.

Find the most valuable subset of items that can fit into the knapsack.

Exhaustive Algorithm

Approach:

• Try every subset of $n$ given items.
• Compute total wight of each subset.
• Compute total value of those subsets that do not exceed knapsack’s capacity.
• Pick the subset that has the largest value.

Analysis:

• There are $2^n-1$ subsets to consider.
  • This is exponential in $n$.

Example

Consider the following values:

• Item 1
  • $w=10$
  • $v=60$
• Item 2
  • $w=20$
  • $v=100$
• Item 3
  • $w=30$
  • $v=120$
• Knapsack
  • Capacity $=50$

One method of optimising would be to iterate through each combinations of subsets that fit in the knapsack and select the set with the most value:

Subset	Weight	Value
$\emptyset$	0	0
{1}	10	60
{2}	20	100
{3}	30	120
{1, 2}	30	160
{1, 3}	40	180
{2, 3}	50	220
{1, 2, 3}	60	N/A

An issue with this method is that the combinations grow exponentially with additional items.

Greedy Algorithm

Example

Consider the following values:

• Item 1
  • $w=10$
  • $v=60$
• Item 2
  • $w=20$
  • $v=100$
• Item 3
  • $w=30$
  • $v=120$
• Knapsack
  • Capacity $=50$

Pick the item with the next largest value if total weight $\leq$ capacity.

Result:

• Item 3 is picked, total value = 120, total weight = 30.
• Item 2 is picked, total value = 220, total wight = 50.
• Item 1 cannot be picked.

This happens to be optimal.

Time Complexity

First the values need to be sorted. This takes:

\[O(n\log n)\]

Completeness

This algorithm doesn’t always give an optimal solution. Using other modifiers like $\frac v w$ also won’t give optimal solutions.

Approximation Ratio

No matter the input, if a greedy algorithm has an approximation ratio of $\frac1 2$, it will always select a subset with a total value of at least $\frac 1 2$ of the optimal solution.