Multiple 0-1 Knapsack Problem

Share:

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:

  • vs=-1 if n < 2 or m < 1

  • vs=-2 if some p(j) , w(j) or k(i) are not positive

  • vs=-3 if a knapsack cannot contain any item

  • vs=-4 if an item cannot fit into any knapsack

  • vs=-5 if knapsack m contains all the items

  • vs=-7 if array k is not correctly sorted

  • vs=-8 [should not happen]

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)