Copyright	(c) Masahiro Sakai 2015
License	BSD-style
Maintainer	masahiro.sakai@gmail.com
Stability	provisional
Portability	non-portable
Safe Haskell	Safe-Inferred
Language	Haskell2010
Extensions	ScopedTypeVariables BangPatterns FlexibleContexts ExplicitForAll

ToySolver.Combinatorial.SubsetSum

Description

References

D. Pisinger, "An exact algorithm for large multiple knapsack problems," European Journal of Operational Research, vol. 114, no. 3, pp. 528-541, May 1999. DOI:10.1016/s0377-2217(98)00120-9 http://www.sciencedirect.com/science/article/pii/S0377221798001209 http://www.diku.dk/~pisinger/95-6.ps

Synopsis

Documentation

Arguments

:: Vector v Weight
=> v Weight	weights `[w1, w2 .. wn]`
-> Weight	l
-> Maybe (Vector Bool)	the assignment `[x1, x2 .. xn]`, identifying 0 (resp. 1) with `False` (resp. `True`).

Solve Σ_{i=1}^n wi xi = c and xi ∈ {0,1}.

Note that this is different from usual definition of the subset sum problem, as this definition allows all xi to be zero.

Note: 0 (resp. 1) is identified with False (resp. True) in the assignment.

Arguments

:: Vector v Weight
=> v Weight	weights `[w1, w2 .. wn]`
-> Weight	capacity `c`
-> Maybe (Weight, Vector Bool)	the objective value Σ_{i=1}^n wi xi, and the assignment `[x1, x2 .. xn]`, identifying 0 (resp. 1) with `False` (resp. `True`).

Maximize Σ_{i=1}^n wi xi subject to Σ_{i=1}^n wi xi ≤ c and xi ∈ {0,1}.

Note: 0 (resp. 1) is identified with False (resp. True) in the assignment.

Arguments

:: Vector v Weight
=> v Weight	weights `[w1, w2 .. wn]`
-> Weight	l
-> Maybe (Weight, Vector Bool)	the objective value Σ_{i=1}^n wi xi, and the assignment `[x1, x2 .. xn]`, identifying 0 (resp. 1) with `False` (resp. `True`).

Minimize Σ_{i=1}^n wi xi subject to Σ_{i=1}^n wi xi ≥ l and xi ∈ {0,1}.

Note: 0 (resp. 1) is identified with False (resp. True) in the assignment.