Today I’d like to share with you a puzzle I managed to solve in past few weeks using a technique called branch&bound – Knapsack.

Interested what is 0-1 Knapsack puzzle about?

The **knapsack problem** (or **rucksack problem)** is a problem in combinatorial optimization: Given a set of items, each with a mass and a value, determine for each item if it can be included in a collection so that the total weight is less than or equal to a given limit (capacity of rucksack) and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items – i.e. Indiana Jones 🙂

The problem often arises in resource allocation where there are financial constraints and is studied in fields such as combinatorics, computer science, complexity theory, cryptography and applied mathematics.

The most common problem being solved is the **0-1 knapsack problem**, which restricts the number *x _{i}* of copies of each kind of item to zero or one.

Mathematically the 0-1-knapsack problem can be formulated as:

- Let there be
*n*items,*x*to_{1}*x*where_{n}*x*has a value_{i}*v*and weight_{i}*w*_{i} - The maximum weight that we can carry in the bag is
*W* - It is common to assume that all values and weights are non negative
- To simplify the representation, we also assume that the items are listed in increasing order of weight.

- Solution is to maximize subject to
- Said by human language: Maximize the sum of the values of the items in the knapsack so that the sum of the weights must be less than the knapsack’s capacity.

## Solution spoiler in Python

Simple knapsack solution:

Input data to function *solveKnapsack* are in format

N W

v_{1} w_{1}

v_{2} w_{2}

….

v_{n-1} w_{n-1}

Where *N* is number of items, *W* is capacity of knapsack.

Each of the following lines contains value *v* and weight *w* of an item.

```
class Item:
def __init__(self, v=0, w=0, w_v=0, idx=0):
self.value = v
self.weight = w
self.importance = w_v
self.original_order = idx
class State:
def __init__(self, item_index = 0, current_value=0, remaining_capacity =0, max_possible_value = 0, path = ""):
self.item_index = item_index
self.current_value = current_value
self.remaining_capacity = remaining_capacity
self.max_possible_value = max_possible_value
self.path = path
# Function that returns maximal possible gain for items
# that are still not processed and for given capacity
def getMaxPossible(items, item_index, current_value, capacity):
max_possible = 0
for i in range(item_index, len(items)):
# If the capacity is less than weight of the item,
# we add "part" of the value equal to "part" of the weight of the item
if items[i].weight > capacity:
max_possible += float(items[i].importnace) * capacity
break
else:
max_possible += items[i].value
capacity -= items[i].weight
return int(max_possible+0.5)+current_value
# Iterative Knapsack solution
# using Depth First Branch&Bound
def knapsack_DFS(items, max_capacity):
optimal_value = 0
target = 0
optimal_path = ""
num_items = len(items)
# Sort all items by their importance
items.sort(key=lambda x: x.importance, reverse=True)
# Initial status of the knapsack
states = [State(0,0,max_capacity,getMaxPossible(items,0,0,max_capacity), "")]
# Compute while there's any unprocessed status
while(len(states)!=0):
# Get the last inserted status
best = states.pop()
# We're processing the last item
if best.item_index == num_items-1:
# We can add the item in the bag
if best.remaining_capacity >= items[best.item_index].weight:
# Item added to the bag gives us the best solution found so far
if best.max_possible_value >= target:
optimal_value = best.max_possible_value
target = optimal_value + 1
optimal_path = ','.join(filter(None, [best.path, str(items[best.item_index].original_order)]))
# We can't add the item into the bag
else:
# Is the solution we found better than the one we've found so far?
if best.current_value >= target:
optimal_value = best.current_value
target = optimal_value + 1
optimal_path = best.path
# Delete all states from queue where the max possible gain is less than gain we reached in the current processing
states = [s for s in states if s.max_possible_value >= target]
# We're not processing the last item
else:
# A) We don't add item in the bag
# Recalculate new maximal possible gain
new_max_possible = getMaxPossible(items, best.item_index+1, best.current_value, best.remaining_capacity)
# Can we do better ?
if new_max_possible >= target:
states.append(State(
best.item_index+1,
best.current_value,
best.remaining_capacity,
new_max_possible,
best.path
)
)
# B) We add item in the bag
if best.remaining_capacity >= items[best.item_index].weight and best.max_possible_value >= target:
states.append(State(
best.item_index+1,
best.current_value+items[best.item_index].value,
best.remaining_capacity - items[best.item_index].weight,
best.max_possible_value,
','.join(filter(None, [best.path, str(items[best.item_index].original_order)]))
)
)
# Format output data
# 1. Optimal value of items added into knapsack
outputData = str(optimal_value) + '\n'
if optimal_path == "":
optimal_path = "0"
# For each item print 1/0 = added/not added into knapsack
picked_list = [x for x in map(int, optimal_path.split(','))]
picked = ""
for x in range(num_items):
if x in picked_list:
picked += "1"
else:
picked += "0"
outputData += " ".join(picked)
return outputData
def solveKnapsack(inputData):
lines = inputData.split('\n')
firstLine = lines[0].split()
num_items = int(firstLine[0])
max_capacity = int(firstLine[1])
items = list()
for i in range(1, num_items+1):
line = lines[i]
parts = line.split()
# Compute item importance (value/weight)
w_v = 0
if int(parts[1]) != 0:
w_v = float(parts[0])/float(parts[1])
items.append(knapsack.Item(int(parts[0]), int(parts[1]), w_v, i-1))
del inputData
del lines
return knapsack_DFS(items, max_capacity)
```

Trying to walk through your code but when I try to run it I get:

NameError: global name ‘knapsack’ is not defined

Hi,

this is most likely due to the

package name– it is not visible in the code.The package where I wrote the code is called ‘knapsack’ and in this package there’s a class called Item.

Hopefully this answers your question 🙂

Thanks, in the end I just changed it to Item and it ran fine as is. Also there is a type on line 23

max_possible += float(items[i].importnace) * capacity

importance is spelled wrong. 🙂

Thank you very much for posting this. I really needed to see it implemented to see what I was doing wrong with my own code.

Thanks…