get.subsetsum {nilde}

Enumeration of all existing 0-1 and bounded solutions of a subset sum problem

Description

By default this function solves the following 0-1 subset sum problem. Given the set of positive integers (a_1, a_2, ..., a_l) and a positive integer n, find all non-empty subsets that sum to n, so that each of the integers a_i either appears in the subset or it does not, and the total number of summands should not exceed M, M <= n.

The bounded subset sum problem has restrictions on the number of times (bounds) a_i can turn up in the subset.

The algorithm is based on a generating function of Hardy and Littlewood used by Voinov and Nikulin (1997).

Usage

 get.subsetsum(a,n,M=NULL,problem="subsetsum01",bounds=NULL)

Arguments

a

An l-vector of positive integers with l>= 2.

n

A positive integer.

M

A positive integer, the maximum number of summands, M <= n

problem

one of the two problems to be solved: "subsetsum01" (default) for a 0-1 subset sum problem, or "bsubsetsum" a bounded subset sum problem.

bounds

An l-vector of positive integers, bounds for s_i, i.e. 0 <= s_i <= b_i

Value

p.n

total number of solutions obtained.

solutions

a matrix with each column presenting a solution for n.

Author(s)

Vassilly Voinov, Natalya Pya Arnqvist, Yevgeniy Voinov

References

Voinov, V. and Nikulin, M. (1997) On a subset sum algorithm and its probabilistic and other applications. In: Advances in combinatorial methods and applications to probability and statistics, Ed. N. Balakrishnan, Birkhäuser, Boston, 153-163.

Hardy, G.H. and Littlewood, J.E. (1966) Collected Papers of G.H. Hardy, Including Joint Papers with J.E. Littlewood and Others. Clarendon Press, Oxford.

See Also

nilde-package, get.partitions, get.knapsack, nlde

Examples

## some examples...
b1 <- get.subsetsum(a=c(41,34,21,20,8,7,7,4,3,3),M=10,n=50,problem="subsetsum01")
b1
colSums(b1$solutions*c(41,34,21,20,8,7,7,4,3,3))

b2 <- get.subsetsum(a=c(111:120),M=10,n=485,problem="subsetsum01") ## no solutions
b2

b3 <- get.subsetsum(a=c(30,29,32,31,33),M=5,n=91,problem="subsetsum01")
b3
colSums(b3$solutions*c(30,29,32,31,33))
get.subsetsum(a=c(30,29,32,31,33),M=5,n=91,problem="bsubsetsum",bounds=c(1,1,1,1,1))

b4 <- get.subsetsum(a=c(30,29,32,31,33),M=5,n=91,problem="bsubsetsum",
                 bounds=c(1,2,1,3,4))
b4
colSums(b4$solutions*c(30,29,32,31,33))