nilde (version 1.1-7)

get.knapsack: Enumeration of all existing nonnegative integer solutions for unbounded, bounded and 0-1 knapsack and subset sum problems

Description

This function solves the unbounded, bounded and 0-1 knapsack problems.

The unbounded knapsack problem can be written as follows.

maximize \(c_1s_1 +c_2s_2 +...+ c_ls_l \)

subject to \(a_1s_1 +a_2s_2 +...+ a_ls_l <= n,\)

\(s_i >= 0, integers.\)

The bounded knapsack problem has additional constraints, \(0 <= s_i <= b_i, i=1,...,l, b_i <= [n/a_i].\) The 0-1 knapsack problem arises when \(s_i= 0\) or \(1, i=1,...,l\).

The algorithm is based on a generating function of Hardy and Littlewood used by Voinov and Nikulin (1997). Subset sum problems are particular cases of knapsack problems when vectors of weights, \((a_1,...,a_l)\), and objectives, \((c_1,...,c_l)\), are equal.

Usage

get.knapsack(objective,a,n,problem="uknap",bounds=NULL)

Value

p.n

total number of solutions obtained.

solutions

a matrix with each column representing a solution of n.

Arguments

objective

A vector of coefficients (values of each item in the knapsack) of the objective function to be maximized when solving knapsack problem.

a

An l-vector of weights of each item in a knapsack, with l>= 2.

n

a maximal possible capacity of the knapsack.

problem

one of the following names of the problems to be solved: "uknap" (default) for an unbounded knapsack problem, "knap01" for a 0-1 knapsack problem, and "bknap" for a bounded knapsack problem.

bounds

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

Author

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.subsetsum, nlde

Examples

## some examples...
b1 <- get.knapsack(objective=c(200:206),a=c(100:106),n=999,problem="uknap")
b1

b2 <- get.knapsack(objective=c(41,34,21,20,8,7,7,4,3,3),a=c(41,34,21,20,8,7,7,4,3,3),
         n=50, problem="bknap", bounds=rep(2,10))
b2
colSums(b2$solutions*c(41,34,21,20,8,7,7,4,3,3))

b3 <- get.knapsack(objective=c(4,3,3),a=c(3,2,2),n=4,problem="bknap",bounds=c(2,2,2))
b3
## get maximum value of the objective function...
colSums(b3$solutions*c(4,3,3)) 
## checking constraint...
colSums(b3$solutions*c(3,2,2))   

b4 <- get.knapsack(objective=c(4,3,3),a=c(3,2,2),n=4,problem="knap01")
b4
## get maximum value of the objective function...
colSums(b4$solutions*c(4,3,3)) 
## checking constraint...
colSums(b4$solutions*c(3,2,2))

if (FALSE) {
b5 <- get.knapsack(a=c(100:106),n=2999,objective=c(200:206),problem="uknap")
b5$p.n ## total number of solutions
options(max.print=5E5)
print(b5)

  }