Skip to content

Instantly share code, notes, and snippets.

@Hepic Hepic/knapsack.py
Created Jan 7, 2018

Embed
What would you like to do?
Branch&Bound Knapsack
import Queue
values = [3, 5, 8, 3, 10, 1]
weights = [1, 2, 5, 2, 8, 3]
best, W, INF = 0, 12, 9999999
class Node(object):
def __init__(self, value, only_int, ind, level):
self.value = value
self.only_int = only_int
self.ind = ind
self.level = level
def __cmp__(self, other):
return self.value < other.value
def tree_format(ind, level):
name = 'S'
for i in range(1, level + 1):
name += '1' if ind & 1 else '0'
ind >>= 1
return name
def integer_solution(initial):
total_w, total_v = 0, 0
for i in range(len(initial)):
total_w += weights[i] * initial[i]
total_v += values[i] * initial[i]
for i in range(len(initial), len(values)):
if total_w + weights[i] <= W:
total_w += weights[i]
total_v += values[i]
return total_v
def linear_solution(initial):
total_w, total_v = 0, 0
only_int = True
for i in range(len(initial)):
total_w += weights[i] * initial[i]
total_v += values[i] * initial[i]
if total_w > W:
return (-INF, 0)
for i in range(len(initial), len(values)):
if total_w + weights[i] <= W:
total_w += weights[i]
total_v += values[i]
else:
total_v += float(W - total_w) / float(weights[i]) * values[i]
only_int = False
break
return (total_v, only_int)
def solve(choice):
global best
cont = Queue.Queue()
if choice == 2:
cont = Queue.LifoQueue()
elif choice == 3:
cont = Queue.PriorityQueue()
curr_sol, only_int = linear_solution([])
cont.put(Node(curr_sol, only_int, 0, 0))
while not cont.empty():
elem = cont.get()
if elem.level > len(values):
continue
print tree_format(elem.ind, elem.level), elem.value
if elem.only_int:
best = max(best, elem.value)
if elem.value <= best:
continue
initial, num = [], elem.ind
for i in range(elem.level):
initial.append(num & 1)
num >>= 1
list_right = initial + [1]
list_left = initial + [0]
curr_sol, only_int = linear_solution(list_right)
cont.put(Node(curr_sol, only_int, (1 << elem.level) + elem.ind, elem.level + 1))
curr_sol, only_int = linear_solution(list_left)
cont.put(Node(curr_sol, only_int, elem.ind, elem.level + 1))
def main():
global best
best = integer_solution([])
choice = 0
while choice < 1 or choice > 3:
choice = input('Enter your choice/number -> Queue(1), Stack(2), PriorityQueue(3): ')
solve(choice)
if __name__ == "__main__":
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.