# Example of use of the Pulp libray for 15-382
# Modeling and solution of a simple knapsack problem
# Gianni A. Di Caro 
#
from pulp import *
import time

# https://pythonhosted.org/PuLP/pulp.html

#
# A list of tuples of items (value, weight)
#
items = [(20,5), (30,6), (10,7), (90,32), (10,2), (40,5), (100,7), (60,9), (70,12), (50,11), (30,1), (20,2)]

# number of items
itemCount = len(items)

# Knapsack max weight capacity
binCapacity = 32


# Decision variables (array), x[i] gets 1 when item i is included in the solution
x = pulp.LpVariable.dicts('item', range(itemCount),
                            lowBound = 0,
                            upBound = 1,
                            cat = 'Integer')

# Initialize the problem and specify the type
problem = LpProblem("Knapsack Problem", LpMaximize)

# Add the objective function
problem += lpSum([ x[i] * (items[i])[0] for i in range(itemCount) ]), "Objective: Maximize profit"

# Capacity constraint: the sum of the weights must be less than the capacity
problem += lpSum([ x[i] * (items[i])[1] for i in range(itemCount) ]) <= binCapacity, "Constraint: Max capacity"

#print problem.constraints

# Write the model to disk, not necessary
problem.writeLP("Knapsack.lp")

# Solve the optimization problem
start_time = time.time()
problem.solve()
print("Solved in %s seconds." % (time.time() - start_time))

# Was the problem solved to optimality?
print("Status:", LpStatus[problem.status])

# Each of the variables is printed with it's resolved optimum value
for v in problem.variables():
    print(v.name, "=", v.varValue)

# The optimised objective function value is printed to the screen
print("Total profit = ", value(problem.objective))

# Some more info about the solution (only variables / items that are selected)
used_cap = 0.0
print "Used items:"
for i in range(itemCount):
    if x[i].value() == 1:
        print i, items[i]
        used_cap += items[i][1]
print "Profit: %d - Used capacity: %d (/ %d)" % (value(problem.objective), used_cap, binCapacity)