change_making function

Change Making Problem

Solves the Change Making problem as an integer linear program.

change_making(items, value)

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.

Returns

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.

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)

## Not run:

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
## End(Not run)