implementation of knapsack problem exploring the state space in a breadth first search manner and using memoization to reduce the exploration space

knapsack_breadth_first_search

# Author: Pedro Borges
import heapq
import sys

def knapsack(val, wt, total_w):
    elements = transform_to_list_dict(val, wt)
    open_list = []
    closed_list = []
    # set to mark the nodes already seen
    generated_nodes = set()
    open_list.append({'state':[], 'remaining': elements})
    while open_list:
        # explore and expand
        last_poped_state = explore_and_expand(closed_list, open_list, generated_nodes, total_w)
    return -heapq.heappop(closed_list)[0] 

def explore_and_expand(closed_list, open_list, generated_nodes, total_w):
    state = open_list.pop(0)
    # explore
    state_weight = sum(i['wt'] for i in state['state'])
    state_sum = sum(i['val'] for i in state['state']) if state_weight <= total_w else float('-inf')
    heapq.heappush(closed_list, (-state_sum, get_hashable(state)))
    #expand
    expand(state, open_list, generated_nodes)
    return state
        
def expand(state, open_list, generated_nodes):
    for i in range(len(state['remaining'])):
        copy_values = state['state'].copy()
        # appends the child to the state
        copy_values.append(state['remaining'][i])
        # removes the child that was append to the state
        copy_children = state['remaining'].copy()
        copy_children.pop(i)
        # appends to be explored
        new_state = {'state':copy_values, 'remaining': copy_children}
        if tuple(get_hashable(new_state)) not in generated_nodes:
            open_list.append(new_state)
            # adds to the set of seen nodes
            generated_nodes.add(get_hashable(new_state))
    return None

def transform_to_list_dict(val, wt):
    res = []
    for i in range(len(val)):
        res.append({'val': val[i], 'wt': wt[i]})
    return res

def get_hashable(state):
    vals = tuple([i['val'] for i in state['state']])
    wts = tuple([i['wt'] for i in state['state']])
    return vals, wts

val = [60, 100, 120]
wt = [10, 20, 30]
total_w = 50
res = knapsack(val, wt, total_w)
res