Packages
fixpoint
0.5.12
0.22.1
0.21.5
0.21.4
0.21.3
0.21.2
0.21.1
0.21.0
0.20.6
0.20.5
0.20.4
0.20.3
0.20.2
0.20.1
0.19.5
0.19.4
0.19.3
0.19.2
0.19.1
0.18.2
0.18.1
0.17.6
0.17.5
0.17.4
0.17.3
0.17.2
0.17.1
0.16.5
0.16.4
0.16.3
0.16.2
0.16.1
0.16.0
0.15.6
0.15.5
0.15.4
0.15.3
0.15.2
0.15.1
0.15.0
0.14.9
0.14.8
0.14.7
0.14.6
0.14.5
0.14.4
0.14.3
0.14.2
0.14.1
0.13.5
0.13.4
0.13.2
0.13.1
0.12.9
0.12.8
0.12.7
0.12.6
0.12.5
0.12.4
0.12.2
0.12.1
0.11.8
0.11.7
0.11.6
0.11.5
0.11.4
0.11.3
0.11.2
0.11.1
0.10.7
0.10.6
0.10.5
0.10.4
0.10.3
0.10.2
0.10.1
0.9.12
0.9.11
0.9.10
0.9.9
0.9.8
0.9.7
0.9.6
0.9.5
0.9.4
0.9.3
0.9.2
0.9.1
0.9.0
0.8.52
0.8.51
0.8.50
0.8.49
0.8.48
0.8.46
0.8.44
0.8.43
0.8.42
0.8.41
0.8.40
0.8.39
0.8.38
0.8.37
0.8.36
0.8.35
0.8.34
0.8.33
0.8.32
0.8.31
0.8.30
0.8.29
0.8.28
0.8.27
0.8.26
0.8.25
0.8.24
0.8.23
0.8.22
0.8.21
0.8.20
0.8.19
0.8.18
0.8.17
0.8.16
0.8.15
0.8.14
0.8.13
0.8.12
0.8.11
0.8.10
0.8.9
0.8.8
0.8.7
0.8.6
0.8.5
0.8.4
0.8.3
0.8.2
0.8.1
0.8.0
0.7.10
0.7.9
0.7.8
0.7.7
0.7.6
0.7.5
0.7.4
0.7.3
0.7.2
0.7.1
0.7.0
0.6.5
0.6.4
0.6.3
0.6.2
0.6.1
0.6.0
0.5.12
0.5.11
0.5.10
0.5.9
0.5.8
0.5.7
0.5.6
0.5.5
0.5.4
0.5.3
0.5.2
0.5.1
0.5.0
0.4.3
0.4.2
0.4.1
0.4.0
0.3.6
0.3.5
0.3.4
0.3.3
0.3.2
0.3.1
0.3.0
0.2.3
0.2.2
0.2.1
0.1.3
0.1.2
0.1.1
0.1.0
Constraint Programming Solver
Current section
Files
Jump to
Current section
Files
lib/examples/knapsack.ex
defmodule CPSolver.Examples.Knapsack do
@moduledoc """
The 'knapsack' problem is mathematically formulated in
the following way. Given n items to choose from, each item i ∈ 0 ...n − 1 has a value v[i] and a
weight w[i]. The knapsack has a limited capacity K. Let x[i] be a variable that is 1 if you choose
to take item i and 0 if you leave item i behind. Then the knapsack problem is formalized as the
following optimization problem:
Maximize sum(x[i]*v[i]), i = 0 ... n - 1
subject to sum(x[i] * w[i]) <= K
Input data:
First line: "n K"
Next lines: "value weight"
"""
alias CPSolver.IntVariable, as: Variable
alias CPSolver.Constraint.Sum
alias CPSolver.Constraint.LessOrEqual
import CPSolver.Variable.View.Factory
def model(values, weights, capacity) do
items = Enum.map(1..length(values), fn i -> Variable.new(0..1, name: "item_#{i}") end)
total_weight = Variable.new(0..capacity, name: "total_weight")
total_value = Variable.new(0..Enum.sum(values), name: "total_value")
constraints = [
Sum.new(
total_weight,
Enum.map(
Enum.zip(items, weights),
fn {item, weight} -> mul(item, weight) end
)
),
Sum.new(
total_value,
Enum.map(
Enum.zip(items, values),
fn {item, value} -> mul(item, value) end
)
),
LessOrEqual.new(total_weight, capacity)
]
%{
# |> Enum.reverse(),
variables: items ++ [total_weight, total_value],
constraints: constraints
}
end
def model(input) do
input
|> File.read!()
|> String.trim()
|> String.split("\n")
|> then(fn lines ->
[header | item_data] = lines
capacity = String.split(header, " ") |> List.last() |> String.to_integer()
{values, weights} =
List.foldr(item_data, {[], []}, fn str, {vals_acc, weights_acc} ->
[v, w] = String.split(str, " ")
{
[String.to_integer(v) | vals_acc],
[String.to_integer(w) | weights_acc]
}
end)
model(values, weights, capacity)
end)
end
end