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?
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
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.
# 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
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