monus-weighted-search-0.2.0.0: Efficient search weighted by an ordered monoid with monus.
Copyright(c) Donnacha Oisín Kidney 2021
Maintainermail@doisinkidney.com
Stabilityexperimental
Portabilitynon-portable
Safe HaskellNone
LanguageHaskell2010

MonusWeightedSearch.Examples.SubsetSum

Description

An implementation of shortest subset sum (the Inclusion-Exclusion method) using the Heap monad.

Synopsis

Documentation

inclusion :: Monad m => HeapT Dist m Bool Source #

A weight for the inclusion or exclusion of an element.

This lets us weight the computation by number of elements included, and therefore optimise for the fewest.

shortest :: Int -> [Int] -> [Int] Source #

shortest n xs returns the shortes subset of xs which sums to n.

>>> shortest 5 [10,-4,3,11,6,12,1]
[-4,3,6]