@@ -0,0 +1,1474 @@
+# Knapsack with backtracking - non-recursive%0A# By James Lao%0A%0Afrom heapq import *%0Aimport time%0Aimport sys%0A%0Adef knapsack(vw, limit):%0A    %0A    def bound(v, w, j):%0A        if j %3E= len(vw) or w %3E limit:%0A            return -1%0A        else:%0A            while j %3C len(vw) and w + vw%5Bj%5D%5B1%5D %3C= limit:%0A                v, w, j = v + vw%5Bj%5D%5B0%5D, w + vw%5Bj%5D%5B1%5D, j + 1%0A            if j %3C len(vw):%0A                v += (limit - w) * vw%5Bj%5D%5B0%5D / (vw%5Bj%5D%5B1%5D * 1.0)%0A            return v%0A%0A    maxValue = 0%0A    stack = %5B%5B0, 0, 0%5D%5D # value, weight, index%0A    counter = 0%0A    %0A    while stack:%0A        counter += 1%0A        v, w, j = stack.pop()%0A        if bound(v, w, j) %3E= maxValue: # promising w/ j%0A            if j %3C len(vw) - 1: %0A                stack.append(%5Bv, w, j + 1%5D)%0A            if w + vw%5Bj%5D%5B1%5D %3C= limit:%0A                maxValue = max(maxValue, v + vw%5Bj%5D%5B0%5D)%0A                stack.append(%5Bv + vw%5Bj%5D%5B0%5D, w + vw%5Bj%5D%5B1%5D, j + 1%5D)%0A    print(%22Total nodes:%22, counter)%0A    return maxValue%0A            %0Aif __name__ == %22__main__%22:%0A    with open(sys.argv%5B1%5D if len(sys.argv) %3E 1 else sys.exit(1)) as f:%0A        limit, n = map(int, f.readline().split())%0A        vw = %5B%5D                   # value, weight, value density%0A        for ln in f.readlines():%0A            vl, wl = tuple(map(int, ln.split()))%0A            vw.append(%5Bvl, wl, vl / (wl * 1.0)%5D)%0A%0A    start = time.time()%0A    A = knapsack(sorted(vw, key=lambda x : x%5B2%5D, reverse=True), limit)%0A    end = time.time()%0A    print(A)%0A    print(end - start)%0A

Create knapsack_bt_non.py