# get.knapsack: Enumeration of all existing nonnegative integer solutions for... In nilde: Nonnegative Integer Solutions of Linear Diophantine Equations with Applications

## 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

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

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

## Value

 `p.n` total number of solutions obtained. `solutions` a matrix with each column representing a solution of `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.

`nilde-package`, `get.partitions`, `get.subsetsum`, `nlde`
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31``` ```## 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)) ## Not run: 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) ## End(Not run) ```