Knapsack algorithm

knapsack.py

a_weights = [400, 200, 100]
xweights = [100, 200, 300, 500, 100, 200, 600, 100, 100]
W = 500

def one_zero (weights):
    d = 0 # Current disk position
    c = 0 # number of files in the current disk
    disks = []
    n = len(weights)

    for i in xrange(n):
        if weights[i] <= W:
            disks.append(weights[i])
        else:
            continue

        disk_total = disks[d]
        if disk_total <= W:
            for j in xrange(i+1, n):
                if disk_total + weights[j] <= W:
                    disks[d] += weights[j]
                    # Make the weight bigger then
                    # the maximun value so we skip it
                    weights[j] = W + 1
                    break
            d += 1

    return disks

xweights.sort(reverse=True)

disks = one_zero(a_weights[:])
print xweights
print disks
print 'Reqired', len(disks), 'disks'