Comparison of 3 alghoritms for Knapsack problem

knapsack.py

#!/usr/bin/python
# -*- coding: utf-8 -*-

from itertools import combinations
import random
import time
import timeit

"""
Porównaj różne algorytmy rozwiązujące dyskretny problem plecakowy.
"""

def brute_force(capacity, dataset):
    """
    Przegląd zupełny (bruteforce, metoda siłowa) - złożoność 2^n
    """
    number = len(dataset)
    best_cost = None
    best_combination = []
    for way in range(number):
        for comb in combinations(dataset, way + 1):
            weight = sum([item[0] for item in comb])
            cost = sum([item[1] for item in comb])
            if (best_cost is None or best_cost < cost) and weight <= capacity:
                best_cost = cost
                best_combination = [0] * number
                for item in comb:
                    best_combination[dataset.index(item)] = 1
    return best_cost, best_combination

def dynamic_programming(capacity, dataset):
    """
    Rozwiązanie dynamiczne - czas wielomianowy.
    """
    number = len(dataset)
    best_combination = []
    best_cost = 0
    table = [[0 for i in xrange(capacity + 1)] for j in xrange(number + 1)]

    for i in xrange(1, number + 1):
        weight, value = dataset[i-1]
        for w in xrange(1, capacity + 1):
            if weight > w:
                table[i][w] = table[i-1][w]
            else:
                table[i][w] = max(table[i-1][w],
                                  table[i-1][w-weight] + value)
    w = capacity
    for i in xrange(number, 0, -1):
        if table[i][w] != table[i-1][w]:
            weight, value = dataset[i-1]
            best_combination.append(dataset[i-1])
            best_cost += value
            w -= weight
    return best_cost, best_combination

def ratio_greedy(capacity, dataset):
    """
    Zachłanny algorytm aproksymacyjny.
    Sortuje elementy w kolejności malejącej stosunek wartości do wagi przedmiotu. n * log(n) i sortowanie.
    """
    number = len(dataset)
    ratios = [(index, item[1] / float(item[0])) for index, item in enumerate(dataset)]
    ratios = sorted(ratios, key=lambda x: x[1], reverse=True)
    best_combination = [0] * number
    best_cost = 0
    weight = 0
    for index, ratio in ratios:
        if dataset[index][0] + weight <= capacity:
            weight += dataset[index][0]
            best_cost += dataset[index][1]
            best_combination[index] = 1
    return best_cost, best_combination

def measure_time(start):
   	time = timeit.default_timer() - start
	return "%1.13f seconds" % time

if __name__ == '__main__':
   	large_capacity = 20
   	print "Generating random dataset of %s elements..." % large_capacity
   	large_dataset = [(random.randint(1, 10), random.randint(1, 10)) for k in xrange(large_capacity)]
   	print large_dataset

   	print "Testing brute-force alghoritm..."
   	start = timeit.default_timer()
   	print brute_force(large_capacity, large_dataset)
   	print measure_time(start)

   	print "Testing dynamic programming alghoritm..."
   	start = timeit.default_timer()
   	print dynamic_programming(large_capacity, large_dataset)
   	print measure_time(start)

   	print "Testing ratio greedy alghoritm..."
   	start = timeit.default_timer()
   	print ratio_greedy(large_capacity, large_dataset)
   	print measure_time(start)