adagio (version 0.9.2)

change_making: Change Making Problem

Description

Solves the Change Making problem as an integer linear program.

Usage

change_making(items, value)

Value

Returns a list with components count, the number of items used to sum up to the value, and solution, the number of items used per item.

Arguments

items

vector of integer numbers greater than zero.

value

integer number

Details

The Change Making problem attempts to find a minimal combination of items that sum up to a given value. If the items are distinct positive integers, the solution is unique.

If the problem is infeasible, i.e. there is no such combination, the returned count is 0.

The problem is treated as an Integer Linear Program (ILP) and solved with the lp solver in lpSolve.

References

See the Wikipedia article on the "change making problem".

See Also

setcover

Examples

items = c(2, 5, 10, 50, 100)
value = 999
change_making(items, value)

if (FALSE) {
solutions <- numeric(20)
for (m in 1:20) {
    sol <- change_making(items, m)
    solutions[m] <- sol$count
}
solutions
#>  [1] 0 1 0 2 1 3 2 4 3 1 4 2 5 3 2 4 3 5 4 2
}