Python Knapsack Branch and Bound -

i have spent week working on branch , bound code knapsack problem, , have looked @ numerous articles , books on subject. however, when running code don't result expect. input received text file, such this:

12 4 1 1 1 3 2 2 3 

where first line capacity, , each subsequent line value/weight pairs. result using file '8' instead of '10' (unless mistaken , items won't fit in knapsack). here code:

#!/usr/bin/python # -*- coding: utf-8 -*-  import queue collections import namedtuple item = namedtuple("item", ['index', 'value', 'weight', 'level', 'bound', 'contains'])  class node:     def __init__(self, level, value, weight, bound, contains):          self.level = level          self.value = value          self.weight = weight          self.bound = bound          self.contains = contains  def upper_bound(u, k, n, v, w):     if u.weight > k:         return 0      else:         bound = u.value         wt = u.weight         j = u.level + 1          while j < n , wt + w[j] <= k:             bound += v[j]             wt += w[j]             j += 1      # fill knapsack fraction of remaining item             if j < n:                 bound += (k - wt) * (v[j] / w[j])              return bound  def knapsack(items, capacity):     item_count = len(items)     v = [0]*item_count     w = [0]*item_count  # sort items value weight ratio     items = sorted(items, key=lambda k: k.value/k.weight, reverse = true)      i,item in enumerate(items, 0):         v[i] = int(item.value)         w[i] = int(item.weight)      q = queue.queue()      root = node(0, 0, 0, 0.0, [])     root.bound = upper_bound(root, capacity, item_count, v, w)     q.put(root)      value = 0     taken = [0]*item_count     best = set()      while not q.empty():         c = q.get()          if c.bound > value:             level = c.level+1      # check 'left' node (if item added knapsack)         left = node(c.value + v[level], c.weight + w[level], level, 0.0, c.contains[:])         left.contains.append(level)          if left.weight <= capacity , left.value > value:             value = left.value             best |= set(left.contains)          left.bound = upper_bound(left, capacity, item_count, v, w)          if left.bound > value:             q.put(left)          # check 'right' node (if items not added knapsack)         right = node(c.value, c.weight, level, 0.0, c.contains[:])         right.contains.append(level)         right.bound = upper_bound(right, capacity, item_count, v, w)          if right.bound > value:             q.put(right)      b in best:         taken[b] = 1      value = sum([i*j (i,j) in zip(v,taken)])      return str(value) 

are indices off? not traversing tree or calculating bounds correctly?

i think want calculate bound if you're not taking item. if take item, means bound still attainable. if don't, have readjust expectations.