Classical Greedy Problem
Continuing with our Greedy Strategy we examine a classical problem of Knapsack.
The problem is relatively simple,
Given N items with different weights, find the maximum weight we can fit into a Knapsack of capacity C.
Naive Solution
First let’s think of a very simple solution.
- We start with one item and if we can fit that item in our Knapsack we keep it.
- We examine the remaining items one by one and keep the item if we can place it in our Knapsack.
- Once this process is over, we repeat the above process but starting with an item we’ve not already started with in the past.
The Naive solution is bound to give us the correct solution since we examine each possible way in which we can keep items in the knapsack and then we can figure out the maximum value of Knapsack by finding the largest one.
It turns out though this is really really slow. The following code snippet shows how it can be done in Go.
The code uses a recursive strategy to find out the value of a knapsack and then compares it to the current maximum knapsack value.
var callStack int
var DoPrint string
//This is for printing the call stack in a manner
//that it's readable and mapped to each call of the
//recursive function.
func init() {
callStack = 0
}
func printSpaces() {
if DoPrint == "" {
return
}
for i := 0; i < callStack; i++ {
fmt.Printf("-")
}
}
//We need a way for us to bind value and weight so we can
//manipulate them together instead of working in indices always.
//This is ofcourse an internal structure
type item struct {
weight int
value int
seen bool
}
func knapsackNaiveDriver(capacity int, items []item) int {
maxValue := 0
if capacity <= 0 {
return 0
}
callStack++
printSpaces()
if DoPrint != "" {
fmt.Printf(">Calculating maximum for size %d\n", capacity)
}
for i := 0; i < len(items); i++ {
//Don't look at the item already seen so far.
if items[i].seen {
continue
}
if items[i].weight <= capacity {
items[i].seen = true
printSpaces()
if DoPrint != "" {
fmt.Printf(">Selected %d\n", items[i].value)
}
callStack++
lesserBag := knapsackNaiveDriver(capacity-items[i].weight, items)
if lesserBag+items[i].value > maxValue {
maxValue = lesserBag + items[i].value
printSpaces()
if DoPrint != "" {
fmt.Printf("Picking item %d with value %d, currentMax = %d\n",
i, items[i].value, maxValue)
}
}
items[i].seen = false
callStack--
}
}
callStack--
return maxValue
}
func KnapsackNaive(capacity int, weights, values []int) int {
var items []item
for i := 0; i < len(weights); i++ {
it := item{weight: weights[i], value: values[i], seen: false}
items = append(items, it)
}
return knapsackNaiveDriver(capacity, items)
}
Correcting the Slowness
The slowness of the algorithm above arises from the fact that we are recomputing some of the values a lot of times which is what making it slower. Let’s take an example
| Item 1 | Item 2 | Item 3 | Item 4 | Item 5 |
If we start with Item 1, then for the remaining Knapsack capacity we can choose from the rest of the items. Considering there are N such items we can say that for every Knapsack capacity remaining we’ll either be able to choose an item or not. Thus,
MAP[SIZE] = MAP[SELECTED ITEMS]
That is, for a particular knapsack size we’ll have a map of values where an item may or may not be present.
If we consider items to be bits of a number then we can describe selected items using a number.
Though this will make things a quite a bit faster but we would require auxiliary storage, in addition the number of items might be large and we might’ve to use a String representation of selected items since it may not fit into a number, for example say N=1000 items.
Employing a Greedy Strategy
Since we want to maximize the Knapsack value a simple change to our algorithm can do the trick. Why not pick up the item with largest value we can fit in knapsack everytime?
Well let’s try it out, assume that we’ve the following items
| Item | Item 1 | style="color:white;background-color:red;">Item 2 | style="color:white;background-color:green;">Item 3 |
|---|---|---|---|
| Value | 9 | 7 | 8 |
| Weight | 5 | 3 | 4 |
If the Knapsack Capacity is 7 what will be the largest Knapsack value?
If we try with our current greedy algorithm that gives us 9 (Item 1) however we can see that it’s actually 15 (Item 2 + Item 3). So we need a little tweak in our greedy algorithm.
Most of the time there are going to be more than 1 constraint to apply to our greedy algorithm. We just need to find out a mathematical model to fit those constraints into. In the case of Knapsack we want to pick the item which has lowest weight and highest value. Thus if we pick items based on the maximum Value / Weight we’ll have our greedy algorithm correct.
In the above table, the Value / Weight is in the following order
- Item 2 ( 7 / 3)
- Item 3 (8 / 4)
- Item 1 (9 / 5)
So our greedy algorithm works out as follows
- Find the item which has maximum Value / Weight
- If we can keep this item in Knapsack, i.e. Weight <= current capacity then keep it
- Repeat this process until we’ve looked over all items or we don’t have any space left in Knapsack.
Unfortunately while this works for fractional Knapsack, i.e. where we can even take piece of an item not whole. This doesn’t work when we want to pick up the whole item. The simple reason being the Lemma isn’t satisfied that we’ll always pickup the item with the largest value / weight value since it’s possible we’re not able to pick up the item wholly.
Faster Algorithm when choosing item Wholly
For every item there are exactly two possibilities
- We pick that item and it increases the value of knapsack.
- We don’t pick that item and check remaining items.
In pseudo code we can do something like
- Check if we can pick the item
- If we can then calculate the new value of knapsack as this item + largest value of remaining knapsack capacity.
- If we can’t pick up this item then for this capacity maximum value will be that of the remaining elements with same capacity we started with when we checked this item.
- Check the bigger of two and set that as maximum for this capacity.
The KnapsackNaive solution is slow because it re-calculates a lot of subproblems. We can speed this up by saving these calculations since for a given capacity and a set of items this value can’t change.
NOTE: We need to do this for every capacity we can encounter. The following code snippet is in go.
func knapsackFastDriver(capacity int, items []item) int {
maxValue := 0
callDepth += 1
defer decreaseAndSetCallDepth()
if len(items) == 0 || capacity == 0 {
hits += 1
return maxValue
}
if knapsackFastMap == nil {
knapsackFastMap = make(map[int]map[int]int)
}
if _, ok := knapsackFastMap[capacity]; ok {
if _, ok = knapsackFastMap[capacity][len(items)]; ok {
hits += 1
return knapsackFastMap[capacity][len(items)]
}
}
miss += 1
//If we're able to pick this item in knapsack.
max1 := 0
if items[0].weight <= capacity {
lesserKnapsackValue := knapsackFastDriver(capacity-items[0].weight, items[1:])
max1 = items[0].value + lesserKnapsackValue
}
//If we're not able to pick this item in knapsack
max2 := knapsackFastDriver(capacity, items[1:])
//Choose the bigger of when we pick and when we don't
if max1 > max2 {
maxValue = max1
} else {
maxValue = max2
}
if _, ok := knapsackFastMap[capacity]; !ok {
knapsackFastMap[capacity] = make(map[int]int)
}
knapsackFastMap[capacity][len(items)] = maxValue
return maxValue
}
You can follow along with the complete code at
Note: The Naive solution is very slow and benchmarking it for anything beyond 50 items may not work.