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 the
number of each item to include in a collection so that the total weight
is less than or equal to a given limit 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.
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. (http://en.wikipedia.org/wiki/Knapsack_problem)
So the goal here is to program the following model.
Maximize
subject to
We are going to use dynamic programming technique to code the problem in python.
Input Format
A knapsack input contains n + 1 lines. The first line contains two integers, the first is the number of items in the problem, n. The second number is the capacity of the knapsack, W. The remaining
lines present the data for each of the items. Each line, i ∈ 0 . . . n − 1 contains two integers, the
item’s value v i followed by its weight w i .
Input File content Format
n W
v_0 w_0
v_1 w_1
...
v_n-1 w_n-1
The output contains a knapsack solution and is made of two lines. The first line contains two values
obj and opt. obj is the total value of the items selected to go into the knapsack (i.e. the objective
value). opt should be 1 if your algorithm proved optimality and 0 otherwise. The next line is a list
of n 0/1-values, one for each of the x i variables. This line encodes the solution.
the solver.py file contains the code that implements the dynamic programming way of knapsack problem. solver.py
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. (http://en.wikipedia.org/wiki/Knapsack_problem)
So the goal here is to program the following model.
Maximize
subject to
We are going to use dynamic programming technique to code the problem in python.
Input Format
A knapsack input contains n + 1 lines. The first line contains two integers, the first is the number of items in the problem, n. The second number is the capacity of the knapsack, W. The remaining
lines present the data for each of the items. Each line, i ∈ 0 . . . n − 1 contains two integers, the
item’s value v i followed by its weight w i .
Input File content Format
n W
v_0 w_0
v_1 w_1
...
v_n-1 w_n-1
The output contains a knapsack solution and is made of two lines. The first line contains two values
obj and opt. obj is the total value of the items selected to go into the knapsack (i.e. the objective
value). opt should be 1 if your algorithm proved optimality and 0 otherwise. The next line is a list
of n 0/1-values, one for each of the x i variables. This line encodes the solution.
the solver.py file contains the code that implements the dynamic programming way of knapsack problem. solver.py
#!/usr/bin/python
# -*- coding: utf-8 -*-
from collections import namedtuple
Item = namedtuple("Item", ['index', 'value', 'weight'])
def solve_it(input_data):
# parse the input
lines = input_data.split('\n')
firstLine = lines[0].split()
item_count = int(firstLine[0])
capacity = int(firstLine[1])
items = []
for i in range(1, item_count+1):
line = lines[i]
parts = line.split()
items.append(Item(i-1, int(parts[0]), int(parts[1])))
value = 0
weight = 0
taken = [0]*len(items)
#create [2 by capacity+1] dimensioned capacity matrix
#use dynamic programming
n_rows=capacity+1
n_cols=item_count+1
cap_matrix = [[0]*(2) for i in range(n_rows)]
for col_item in range(1,n_cols):
for row in range(1,n_rows):
if items[col_item-1].weight <= row:
#check if not taking current item yields in a better value
cap_matrix[row][1] = max(cap_matrix[row-items[col_item-1].weight][0] + items[col_item-1].value, cap_matrix[row][0])
else:
#our item doesnt fit yet get the value of previous item
cap_matrix[row][1] = cap_matrix[row][0]
f = open("helper.txt", "w")
f.write(mylist)
#set the optimum value
value = cap_matrix[n_rows-1][n_cols-1]
#print the capacity matrix
#print('\n'.join([''.join(['{:4}'.format(item) for item in row])
# for row in cap_matrix]))
#lets traceback to see which items are taken
n_cols = n_cols-1
n_rows = n_rows-1
while(n_rows>0 and n_cols>0):
if(cap_matrix[n_rows][n_cols] != cap_matrix[n_rows][n_cols-1]):
n_cols = n_cols-1
taken[n_cols] =1 #item selected
n_rows = n_rows - items[n_cols].weight #decrease capacity by items weight
else:
n_cols = n_cols-1
taken[n_cols] =0
# prepare the solution in the specified output format
output_data = str(value) + ' ' + str(0) + '\n'
output_data += ' '.join(map(str, taken))
return output_data
import sys
if __name__ == '__main__':
if len(sys.argv) > 1:
file_location = sys.argv[1].strip()
input_data_file = open(file_location, 'r')
input_data = ''.join(input_data_file.readlines())
input_data_file.close()
print solve_it(input_data)
else:
print 'This test requires an input file. Please select one from the data directory. (i.e. python solver.py ./data/ks_4_0)'
