adagio (version 0.5.9)

mknapsack: Multiple 0-1 Knapsack Problem

Description

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

Usage

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.

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.

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) <= 1="" k(i)="" for="" i="1,...,m" x(1,j)="" +="" ...="" x(m,j)="" <="1" j="1,...,n" x(i,j)="0" or="" ,="" ,<="" code="">

The input problem description must satisfy the following conditions:

• vs=-1if n < 2 or m < 1
• vs=-2if some p(j) , w(j) or k(i) are not positive
• vs=-3if a knapsack cannot contain any item
• vs=-4if an item cannot fit into any knapsack
• vs=-5if knapsack m contains all the items
• vs=-7if array k is not correctly sorted
• vs=-8[should not happen]

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

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