v2

from collections import namedtuple
from collections import deque
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 = deque()
    nodeQueue.append(root)

    while nodeQueue:
        n = nodeQueue.popleft()
        if (n.totalBenefit > bestSolution.totalBenefit):
            bestSolution = n
        for i in range(len(items)):
            #if i not in n.addedItems and n.totalWeight + items[i].weight < maxWeight:
            if (not n.addedItems or i > n.addedItems[-1]) and n.totalWeight + items[i].weight < maxWeight:
                nodeQueue.append(Node(apnd(n.addedItems, i), n.totalBenefit + items[i].benefit, n.totalWeight + items[i].weight))

    return bestSolution

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

    while nodeStack:
        n = nodeStack.pop()
        if (n.totalBenefit > bestSolution.totalBenefit):
            bestSolution = n
        for i in range(len(items)):
            #if i not in n.addedItems and n.totalWeight + items[i].weight < maxWeight:
            if (not n.addedItems or i > n.addedItems[-1]) and n.totalWeight + items[i].weight < maxWeight:
                nodeStack.append(Node(apnd(n.addedItems, i), n.totalBenefit + items[i].benefit, n.totalWeight + items[i].weight))

    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, 100),
    Item(25, 63),
    Item(64, 120),
    Item(54, 77),
    Item(18, 6),
    Item(46, 93),
    Item(28, 35),
    Item(61, 45),
    Item(45, 65),
    Item(88, 100),
    Item(10, 30),
    Item(23, 43),
    Item(155, 400),
    Item(12, 53),
    Item(0, 500)
    ]

print("BFS...")
startTime = time.time()
solutionBFS = solveKnapsackBFS(items, 1000)
endTime = time.time()
print("Best solution was the following sequence")
for i in solutionBFS.addedItems:
    print("%d: %d %d" % (i, items[i].benefit, items[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, 1000)
endTime = time.time()
print("Best solution was the following sequence")
for i in solutionDFS.addedItems:
    print("%d: %d %d" % (i, items[i].benefit, items[i].weight))
print("Total benefit was %d, total weight %d" % (solutionDFS.totalBenefit, solutionDFS.totalWeight))
print("Time taken: %.2fs" % (endTime - startTime))