branch and bound

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

from collections import namedtuple
Item = namedtuple("Item", ['index', 'value', 'weight'])


def estimate(items, capacity):
    value = 0
    weight = 0

    ratios = [(item, float(item.value)/float(item.weight)) for item in items]
    global total_value
    total_value = sum([item.value for item in items])
    ratios = [item[0] for item in reversed(sorted(ratios, key=lambda (item, ratio): ratio))]
    taken = [0]*len(items)

    for item in ratios:
        if weight + item.weight <= capacity:
            taken[item.index] = 1
            value += item.value
            weight += item.weight

        else:
            rest = capacity - weight
            value += item.value * rest/float(item.weight)

    return value


def neighbors(state, length, items):
    global total_value
    return_value = []
    print state
    old_state = state[0][0]
    value = state[0][1]
    rest_capacity = state[0][2]
    curr_estimation = state[0][3]
    right_state = old_state + [1]
    left_state = old_state + [0]
    current_pos = len(old_state)
    estim = estimation(old_state, curr_estimation, items)
    if current_pos < length:
        left = [(left_state, value, rest_capacity, curr_estimation)]
        if rest_capacity - items[current_pos].weight > 0:
            right = [(right_state, value + items[current_pos].value, rest_capacity - items[current_pos].weight, estim)]
            return_value = [left, right]
        else:
            return_value = [left]

    return return_value


def estimation(state, total, items):
    t = total
    for i in range(len(state)):
        if state[i] == 0:
            t -= items[i].value
    return min(t, total)


def solve_it(input_data):
    # Modify this code to run your optimization algorithm

    # parse the input
    lines = input_data.split('\n')

    firstLine = lines[0].split()
    item_count = int(firstLine[0])
    capacity = int(firstLine[1])

    items = []

    for i in range(1, item_count+1):
        line = lines[i]
        parts = line.split()
        items.append(Item(i-1, int(parts[0]), int(parts[1])))


    # a trivial greedy algorithm for filling the knapsack
    # it takes items in-order until the knapsack is full

    estimation = estimate(items, capacity)

    fringe = []
    #fringe.append(0, capacity, estimation)

    state = [([], 0, capacity, estimation)]
    fringe.append(state)

    while len(fringe) > 0:
        state = fringe.pop()
        nodes = neighbors(state, item_count, items)
        for node in nodes:
            if node:
                fringe.append(node)
                print node




    value = 0
    weight = 0

    ratios = [(item, float(item.value)/float(item.weight)) for item in items]
    ratios = [item[0] for item in reversed(sorted(ratios, key=lambda (item, ratio): ratio))]
    taken = [0]*len(items)

    for item in ratios:
        if weight + item.weight <= capacity:
            taken[item.index] = 1
            value += item.value
            weight += item.weight

        else:
            rest = capacity - weight
            value += item.value * rest/float(item.weight)

    # prepare the solution in the specified output format
    output_data = str(value) + ' ' + str(0) + '\n'
    output_data += ' '.join(map(str, taken))
    return output_data


import sys

if __name__ == '__main__':
    #if len(sys.argv) > 1:
    file_location = 'data/test.data'   #sys.argv[1].strip()
    input_data_file = open(file_location, 'r')
    input_data = ''.join(input_data_file.readlines())
    input_data_file.close()
    print solve_it(input_data)
    #else:
    #print 'This test requires an input file.  Please select one from the data directory. (i.e. python solver.py ./data/ks_4_0)'