# Knapsack problem¶

My knapsack holds at most 15kg. I have the following items:

Item number 1 2 3 4 5
weight (kg) 12 2 4 1 1
value ($) 4 2 10 2 1 How can maximize the value of the items in my knapsack? ### First formulation¶ In [7]: using JuMP, Cbc m = Model(solver=CbcSolver()) @variable(m, z[1:5], Bin ) @constraint(m, 12z[1] + 2z[2] + 4z[3] + z[4] + z[5] <= 15) @objective(m, Max, 4z[1] + 2z[2] + 10z[3] + 2z[4] + 1z[5]) status = solve(m) println(m) println(status) println() println("z = ", getvalue(z) ) println("objective = ", getobjectivevalue(m) )  Max 4 z[1] + 2 z[2] + 10 z[3] + 2 z[4] + z[5] Subject to 12 z[1] + 2 z[2] + 4 z[3] + z[4] + z[5] <= 15 z[i] in {0,1} for all i in {1,2,3,4,5} Optimal z = [0.0, 1.0, 1.0, 1.0, 1.0] objective = 15.0  ### General formulation¶ Suppose we have weights$w_1,\dots,w_n$and a weight limit$W$. Suppose the items have values of$v_1,\dots,v_n\$. How should we choose the items in order to maximize value while satisfying weight limit.

In [10]:
# parameters for our problem
w = [12, 2, 4, 1, 1]  # weights
v = [4, 2, 10, 2, 1]  # values
W = 15                # weight limit
n = length(w);        # number of items

In [11]:
using JuMP, Cbc

m = Model(solver=CbcSolver())
@variable(m, z[1:n], Bin )
@constraint(m, sum( w[i]*z[i] for i=1:n) <= W )
@objective(m, Max, sum( v[i]*z[i] for i=1:n) )

status = solve(m)

println(m)
println(status)
println()
println("z = ", getvalue(z) )
println("objective = ", getobjectivevalue(m) )

Max 4 z[1] + 2 z[2] + 10 z[3] + 2 z[4] + z[5]
Subject to
12 z[1] + 2 z[2] + 4 z[3] + z[4] + z[5] <= 15
z[i] in {0,1} for all i in {1,2,3,4,5}

Optimal

z = [0.0, 1.0, 1.0, 1.0, 1.0]
objective = 15.0

In [ ]: