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 xi 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, x1 to xn where xi has a value vi and weight wi
- 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
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.split() num_items = int(firstLine) max_capacity = int(firstLine) 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) != 0: w_v = float(parts)/float(parts) items.append(knapsack.Item(int(parts), int(parts), w_v, i-1)) del inputData del lines return knapsack_DFS(items, max_capacity)