Knapsack Algorithm: A Dynamic Programming Approach

I thought I might write one algorithm that I find really interesting: Knapsack problem.

Its problem statement is simple:

  • You have a fixed-size knapsack (meaning it will only hold at most weight of W, otherwise it will break.
  • You have a set of items, whatever it may be, and each item has its weight and its value.
  • You have to determine the best combination of items so that the value is maximized without overloading your bag.

A problem so simple, yet difficult.  We see it practically everywhere.  Resource allocation is a problem that arises in Business, too.  The problem has also been studied in depth under Complexity Theory, Cryptography, and Combinatorics.  This is the very problem we solve before leaving our house: should I take my laptop?  Do I also take my textbook?  Nah, maybe I’m just gonna drop the knapsack and leave the house with nothing.

A naive way to solve this problem is to go through all the 2^n subsets of the n items that we could possibly add and check whichever gives the maximum output.  We can come up with a usually better solution using dynamic programming.  Just like any other dynamic programming approach, we aim to find an optimal sub-solution to tackle the bigger problem.  We implement a solution to Knapsack problem with the complexity of the algorithm O(nW) (pseudopolynomial of course, as the problem is NP-Hard) as implemented below:

'Author: Ionwyn Sean'

def knapsack(items, weight):

    table = [[0 for w in xrange(weight + 1)] for i in xrange(len(items) + 1)]

    for i in xrange(1, len(items) + 1):
        item_name, item_weight, item_value = items[i-1]
        for w in xrange(1, weight + 1):
            if (item_weight > w):
                table[i][w] = table[i-1][w]
            else:
                table[i][w] = max(table[i-1][w], table[i-1][w-item_weight] + item_value)

    result = []
    w = weight
    for i in xrange(len(items), 0, -1):
        if (table[i][w] != table[i-1][w]):
            item_name, item_weight, item_value = items[i-1]
            result.append(items[i-1])
            w -= item_weight
    return result

# Counts the total weight and total value of items to be added
def totalvalue(comb):
    weight_total = value_total = 0
    for item_name, item_weight, item_value in comb:
        weight_total  += item_weight
        value_total += item_value
    return (value_total, weight_total) if weight_total <= 100 else (0, 0)

And here’s an example on how you can add items to be considered:

'items = ("Item Name", weight, value)'
items = (
    ("Book 1", 20, 150),
    ("Book 2", 20, 100),
    ("Water bottle", 5, 20),
    ("Laptop", 80, 200),
    ("Laptop charger", 10, 70),
    ("Phone charger", 3, 45),
    ("House keys", 3, 200),
    ("Notebook", 15, 70),
    ("Pen and pencil case", 5, 50),
    ("Umbrella", 5, 20),
    ("iPad", 10, 30),
    ("Lecture notes", 10, 50),
    ("Extra Clothings", 10, 25),
    ("Gum", 1, 10),
    ("Hygiene products", 10, 20),
    ("Headphones", 3, 70),
    ("Healthy snacks", 4, 35),
    ("Beer", 2, 40),
    )

And here’s an example of the result:

>>> to_take = knapsack(items, 100)
>>> total_value, total_weight = totalvalue(to_take)
>>> print ("The algorithm suggests taking these items:\n   " + '\n   '.join(sorted(item_name for item_name,_,_ in to_take)) + "\nfor a total value of %i and a total weight of %i" % (total_value, total_weight))
The algorithm suggests taking these items:
   Beer
   Book 1
   Book 2
   Headphones
   Healthy snacks
   House keys
   Laptop charger
   Lecture notes
   Notebook
   Pen and pencil case
   Phone charger
   Water bottle
for a total value of 900 and a total weight of 100
>>>

Notice that the algorithm suggests taking laptop charger without the laptop itself, making it useless to carry a laptop charger (maybe your fellow friend want to borrow it?) because it does not take into account that carrying a laptop charger is useless if you don’t have the laptop.  I leave it to you to implement your own version of Knapsack depending on what you need.

Application:

On one evening at a coffee shop with my friend, he suggested parameterizing my daily activities to numbers: hours you want/need to dedicate for a certain activity, and the rating of a certain activity (based on how happy does doing a certain activity make you, or based on priority).  Though he was not referring to the Knapsack problem, it made me think about the the problem statement is analogous to the Knapsack one: you have 24 hours, there are activities around you that has its hours and value.

I thought this is definitely a brilliant idea, one that I never thought of.  Though, there are improvisations to do with the existing algorithms as it’s not easy to deal with complexities that us humans encounter everyday.

On top of that I thought that maybe we can add the Eisenhower decision matrix as a playing factor in the implementation.  But then again, I have no time to do this just yet.  If you intend to implement such stuff, do let me know and maybe we can collaborate on this project.
For more advanced stuff, there is a fully polynomial approximation scheme (FTPAS) solution for that.  Link leads to a lecture note by Mark de Berg of Eindhoven University of Technology in the Netherlands.

For my lack of understanding of FPTAS, I will not have an implementation of Knapsack FPTAS, yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s