Created
May 17, 2016 16:06
-
-
Save dtroupe18/b482a9cf5ad23fa5596c1029378191a8 to your computer and use it in GitHub Desktop.
0-1 KnapSack Problem
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # items is a set of tuples (itemName, weight, value) | |
| # limit is the max amount of weight the knapsack can hold | |
| # this algorithm assumes each item can only be taken once! | |
| def KnapSack(items, limit): | |
| # initialize a table with all zero values item rows and weight columns! | |
| table = [[0 for w in range(limit + 1)] for j in range(len(items) + 1)] | |
| # iterate over each row | |
| for j in range(0, len(items) + 1): | |
| # picks the items in order (sub-problem) | |
| item, wt, val = items[j - 1] | |
| # iterate over each row (possible weights) | |
| for w in range(1, limit + 1): | |
| # if the weight of item > current possible weight it cannot be added to the sack | |
| if wt > w: | |
| table[j][w] = table[j-1][w] # take the value of the previous row at that weight (sub-problem) | |
| else: | |
| table[j][w]= max(table[j-1][w], table[j-1][w-wt] + val) | |
| # take the sub-problem max or it adds another item to the sack, or exchanges two items | |
| result = [] | |
| w = limit | |
| for j in range(len(items), 0, -1): | |
| was_added = table[j][w] != table[j - 1][w] | |
| # you can tell and item was added to the knapsack when it is not equal to the row above it in the | |
| # same column | |
| if was_added: | |
| item, wt, val = items[j - 1] | |
| result.append(items[j - 1]) # adds the item to the results list | |
| w -= wt # increments the column we are searching | |
| print result | |
| return result | |
| items = ((1, 2, 3), (2, 3, 4), (3, 4, 8), (4, 5, 8), (5, 9, 10)) | |
| KnapSack(items, 20) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment