gistfile1.py

def read_file(filename):
    v = []
    w = []
    capacity = 0
    f = open(filename)
    for line in f:
        if line.startswith("capacity="):
            capacity = int(line[9:])
        else:
            v_, w_ = (eval(line))
            v.append(v_)
            w.append(w_)
    f.close()
    return (v, w, capacity)

def KnapSack(v, w, n, W):
    # build table V and K
    V = []
    keep = []
    for i in range(0,n+1):
        keep.append([False]*(W+1))
        V.append([0]*(W+1))

    # DP algorithm
    for i in range(1,n+1):
        for w_ in range(0,W+1):
            if w[i-1] <= w_ and (v[i-1] + V[i - 1][w_ - w[i-1]] > V[i - 1][w_]):
                V[i][w_] = v[i-1] + V[i - 1][w_ - w[i-1]]
                keep[i][w_] = True
            else:
                V[i][w_] = V[i - 1][w_]
                keep[i][w_] = False

    # find optimal knapsack
    K = W
    optimal_knapsack = []
    for i in range(n, 1, -1):
        if keep[i][K]:
            optimal_knapsack.append((v[i-1], w[i-1]))
            K = K - w[i-1]

    return optimal_knapsack

def main():
    v, w, capacity = read_file("referenceExample.txt")

    print "Optimal knapsack: " + str(KnapSack(v, w, len(v), capacity))

if __name__ == '__main__':
        main()