knapsack_generator_test.py

#!/usr/bin/python2
import random

def knapsacker(items, maxweight):
    # Create an (N+1) by (W+1) 2-d list to contain the running values
    # which are to be filled by the dynamic programming routine.
    #
    # There are N+1 rows because we need to account for the possibility
    # of choosing from 0 up to and including N possible items.
    # There are W+1 columns because we need to account for possible
    # "running capacities" from 0 up to and including the maximum weight W.
    bestvalues = [[0] * (maxweight + 1)
                  for i in xrange(len(items) + 1)]

    # Enumerate through the items and fill in the best-value table
    for i, (value, weight) in enumerate(items):
        # Increment i, because the first row (0) is the case where no items
        # are chosen, and is already initialized as 0, so we're skipping it
        i += 1
        for capacity in xrange(maxweight + 1):
            # Handle the case where the weight of the current item is greater
            # than the "running capacity" - we can't add it to the knapsack
            if weight > capacity:
                bestvalues[i][capacity] = bestvalues[i - 1][capacity]
            else:
                # Otherwise, we must choose between two possible candidate values:
                # 1) the value of "running capacity" as it stands with the last item
                #    that was computed; if this is larger, then we skip the current item
                # 2) the value of the current item plus the value of a previously computed
                #    set of items, constrained by the amount of capacity that would be left
                #    in the knapsack (running capacity - item's weight)
                candidate1 = bestvalues[i - 1][capacity]
                candidate2 = bestvalues[i - 1][capacity - weight] + value

                # Just take the maximum of the two candidates; by doing this, we are
                # in effect "setting in stone" the best value so far for a particular
                # prefix of the items, and for a particular "prefix" of knapsack capacities
                bestvalues[i][capacity] = max(candidate1, candidate2)

    # Reconstruction
    # Iterate through the values table, and check
    # to see which of the two candidates were chosen. We can do this by simply
    # checking if the value is the same as the value of the previous row. If so, then
    # we say that the item was not included in the knapsack (this is how we arbitrarily
    # break ties) and simply move the pointer to the previous row. Otherwise, we add
    # the item to the reconstruction list and subtract the item's weight from the
    # remaining capacity of the knapsack. Once we reach row 0, we're done
    reconstruction = []
    i = len(items)
    j = maxweight
    while i > 0:
        if bestvalues[i][j] != bestvalues[i - 1][j]:
            reconstruction.append(items[i - 1])
            j -= items[i - 1][1]
        i -= 1

    # Reverse the reconstruction list, so that it is presented
    # in the order that it was given
    reconstruction.reverse()

    # Return the best value, and the reconstruction list
    return sum(bestvalues[len(items)][maxweight]) #, reconstruction

def main():
    files = 2
    for filenum in xrange(files):
        rows = random.randint(1, 1000);
        dimension = random.randint(1, 2);
        output = "{}\n{}\n".format(rows, dimension)
        objects = []
        for i in xrange(rows):
            weight = random.uniform(0, 1000)
            cost = 0
            if(dimension == 1):
                cost = random.uniform(0, 1000)
            objects.append((weight, cost))
            output += "{}\n{}\n{}\n".format(str(i), weight, cost)
        
            
        knapsize = random.uniform(0, rows);
        output += "{}\n".format((knapsize))
        f = open('{}.in'.format(filenum), 'w')
        f.write(output)
        f.close()
        output = ""
        """
        # the following will not work
        # unless you change knapsize and cost to integer values
        if dimension == 1:
            print(sorted(objects))
            print(sum(sorted(objects)[:knapsize]))
        else:
            print(knapsacker(objects, knapsize))
        """
    
if __name__ == '__main__':
    main()