from collections import namedtuple
import queue
import time;

Item = namedtuple("Item", "benefit weight")
Node = namedtuple("Node", "addedItems totalBenefit totalWeight")

# Appends a value to the end of a list and returns the new list
def apnd(lst, item):
    nlst = list(lst)
    nlst.append(item)
    return nlst

# Breadth-first search
def solveKnapsackBFS(items, maxWeight):
    root = Node([], 0, 0)
    bestSolution = root
    nodeQueue = queue.Queue()
    nodeQueue.put(root)

    while not nodeQueue.empty():
        n = nodeQueue.get()
        if (n.totalBenefit > bestSolution.totalBenefit):
            bestSolution = n
        for i in items:
            if i not in n.addedItems and n.totalWeight + i.weight < maxWeight:
                nodeQueue.put(Node(apnd(n.addedItems, i), n.totalBenefit + i.benefit, n.totalWeight + i.weight))

    return bestSolution

# Depth-first search
def solveKnapsackDFS(items, maxWeight):
    root = Node([], 0, 0)
    global bestSolution
    bestSolution = root

    def rec(n):
        global bestSolution
        if (n.totalBenefit > bestSolution.totalBenefit):
            bestSolution = n
        for i in items:
            if i not in n.addedItems and n.totalWeight + i.weight < maxWeight:
                rec(Node(apnd(n.addedItems, i), n.totalBenefit + i.benefit, n.totalWeight + i.weight))

    rec(root)

    return bestSolution

# Run both functions on a set of items and measure time
items = [
    Item(20, 15),
    Item(40, 32),
    Item(50, 60),
    Item(36, 80),
    Item(25, 43),
    Item(64, 120),
    Item(54, 77),
    Item(18, 6),
    Item(46, 93),
    Item(28, 35)
    ]

print("BFS...")
startTime = time.time()
solutionBFS = solveKnapsackBFS(items, 420)
endTime = time.time()
print("Best solution was the following sequence")
for i in solutionBFS.addedItems:
    print("%d %d" % (i.benefit, i.weight))
print("Total benefit was %d, total weight %d" % (solutionBFS.totalBenefit, solutionBFS.totalWeight))
print("Time taken: %.2fs" % (endTime - startTime))

print("DFS...")
startTime = time.time()
solutionDFS = solveKnapsackDFS(items, 420)
endTime = time.time()
print("Best solution was the following sequence")
for i in solutionDFS.addedItems:
    print("%d %d" % (i.benefit, i.weight))
print("Total benefit was %d, total weight %d" % (solutionDFS.totalBenefit, solutionDFS.totalWeight))
print("Time taken: %.2fs" % (endTime - startTime))