0-1 Knapsack Problem

getUsedItems.py

# w = list of item weight or cost
# c = the cost matrix created by the dynamic programming solution
def getUsedItems(w,c):
    # item count
    i = len(c)-1
    currentW =  len(c[0])-1
    # set everything to not marked
    marked = []
    for i in range(i+1):
        marked.append(0)      
        while (i >= 0 and currentW >=0):
            if (i==0 and c[i][currentW] >0 )or c[i][currentW] != c[i-1][currentW]:
                marked[i] =1
                currentW = currentW-w[i]
            i = i-1
    return marked

zeroOneKnapsack.py

# v = list of item values or profit
# w = list of item weight or cost
# W = max weight or max cost for the knapsack
def zeroOneKnapsack(v, w, W):
    # c is the cost matrix
    c = []
    n = len(v)
    c = zeros(n,W+1)
    for i in range(0,n):
        # for ever possible weight
        for j in range(0,W+1):    
            # can we add this item to this?
            if (w[i] > j):
                c[i][j] = c[i-1][j]
            else:
                c[i][j] = max(c[i-1][j],v[i] +c[i-1][j-w[i]])
    return [c[n-1][W], getUsedItems(w,c)]

zeros.py

def zeros(rows,cols):
    row = []
    data = []
    for i in range(cols):
        row.append(0)
    for i in range(rows):
        data.append(row[:])
    return data

if (len(sys.argv)!=3):
    print "Usage knapsack.py weight1-profit1,weight2-profit2,... max weight"
    print "Example:"
    print "knapsack.py 1-2,2-5,3-10 12"
    quit()
 
items = sys.argv[1].split(',')
w = []
v = []
total =0
for item in items:
    nums = item.split('-')
    w.append(int(nums[0]))
    v.append(int(nums[1]))
 
maxCost = int(sys.argv[2])
answer = zeroOneKnapsack(v,w,maxCost)
print "if my knapsack can hold %d pounds, i can get %d profit." % (maxCost,answer[0])
print "\tby taking item(s): ",
for i in range(len(answer[1])):
    if (answer[1][i] != 0):
        print i+1,