get.subsetsum function

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

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).

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$

Returns

• 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, , 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))