Description Usage Arguments Value Author(s) References See Also Examples
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.
1 | get.knapsack(objective,a,n,problem="uknap",bounds=NULL)
|
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 |
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. |
p.n |
total number of solutions obtained. |
solutions |
a matrix with each column representing a solution of |
Vassilly Voinov, Natalya Pya Arnqvist, Yevgeniy Voinov
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)
|
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.