knapsack_construction_heuristic.py

def construct_knapsack_solution(weights, values, capacity):
    '''
    Create a fair (initial) knapsack solution

    :param weights: Weights of the objects in the knapsack problem
    :param values: Values assigned to the knapsack items
    :param capacity: Capacity of the knapsack
    :return: an (initial) solution to start knapsack optimization with
    '''
    # enrich list with value/weight for each weight-value tupel
    enriched_list = [(idx, value / weight, weight, value) for idx, weight, value in
                     zip(range(len(weights)), weights, values)]
    # now sort list descending by its value/weight coefficient
    sorted_list = sorted(enriched_list, key=lambda x: x[1], reverse=True)
    # now fill knapsack starting from the most valuable item until no other item fits in
    current_capacity = 0
    current_value = 0
    init_sol = [0] * len(weights)
    for item in sorted_list:
        if capacity - current_capacity >= item[2]:
            init_sol[item[0]] = 1
            current_capacity += item[2]
            current_value += item[3]
    return init_sol, current_value


# Main program
# Knapsack problem definition
weights = [4, 12, 1, 2, 1]
values = [10, 4, 2, 2, 1]
capacity = 15

init_sol, init_val = construct_knapsack_solution(weights, values, capacity)
print("Solution: ", init_sol, ", Value: ", init_val)