mknapsack: Multiple 0-1 Knapsack Problem

Description Usage Arguments Details Value Note Author(s) References See Also Examples

View source: R/mknapsack.R

Description

Solves the 0-1 (binary) multiple knapsack problem.

Usage

1
mknapsack(p, w, k, bck = -1)

Arguments

p

integer vector of profits.

w

integer vector of weights.

k

integer vector of capacities of the knapsacks.

bck

maximal number of backtrackings allowed; default: -1.

Details

Solves the 0-1 multiple knapsack problem for integer profits and weights

A multiple 0-1 knapsack problem can be formulated as:

maximize vstar = p(1)*(x(1,1) + ... + x(m,1)) + ... ... + p(n)*(x(1,n) + ... + x(m,n)) subject to w(1)*x(i,1) + ... + w(n)*x(i,n) <= k(i) for i=1,...,m x(1,j) + ... + x(m,j) <= 1 for j=1,...,n x(i,j) = 0 or 1 for i=1,...,m , j=1,...,n ,

The input problem description must satisfy the following conditions:

Value

A list with compomnents, ksack the knapsack numbers the items are assigned to, value the total value/profit of the solution found, and bs the number of backtracks used.

Note

With some care, this function can be used for the bounded and unbounded single knapsack problem as well.

Author(s)

The Fortran source code is adapted from the free NSCW Library of Mathematical Subroutines.

The wrapping code has been written by yours package maintainer,
HwB email: <hwborchers@googlemail.com>

References

Kellerer, H., U. Pferschy, and D. Pisinger (2004). Knapsack Problems. Springer-Verlag, Berlin Heidelberg.

Martello, S., and P. Toth (1990). Knapsack Problems: Algorithms and Computer Implementations. John Wiley & Sons, Ltd.

See Also

Other packages implementing knapsack routines.

Examples

 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
32
## Example 1: single knapsack
p <- c(15, 100, 90, 60, 40, 15, 10,  1)
w <- c( 2,  20, 20, 30, 40, 30, 60, 10)
cap <- 102
(is <- mknapsack(p, w, cap))
which(is$ksack == 1)
# [1] 1 2 3 4 6 , capacity 102 and total profit 280

## Example 2: multiple knapsack
p <- c(110, 150, 70, 80, 30, 5)
w <- c( 40,  60, 30, 40, 20, 5)
k <- c(65, 85)
is <- mknapsack(p, w, k)
# kps 1: 2,6; kps 2: 1,4; value: 345; backtracks: 14

## Example 3: multiple knapsack
p <- c(78, 35, 89, 36, 94, 75, 74, 79, 80, 16)
w <- c(18,  9, 23, 20, 59, 61, 70, 75, 76, 30)
k <- c(103, 156)
is <- mknapsack(p, w, k)
# kps 1: 1,3,6; kps 2: 4,5,9; value: 452; backtracks: 4 

##  Example 4: subset sum
p <- seq(2, 44, by = 2)^2
w <- p
is <- mknapsack(p, w, 2012)
sum((2 * which(is$ksack == 1))^2)

##  Example 5: maximize number of items
w <- seq(2, 44, by = 2)^2
p <- numeric(22) + 1
is <- mknapsack(p, w, 2012)

adagio documentation built on May 31, 2017, 3:18 a.m.

Search within the adagio package
Search all R packages, documentation and source code