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 [ ]: