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 x_n where x_i has a value v_i and weight 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₁ w₁
v₂ w₂
….
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)