knapsack: The Single Knapsack Problem
In knapsack: Knapsack Routines

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

Solves the 0-1 (single), bounded, and unbounded single knapsack problem.

1	knapsack(profits, weights, capacity, bounds = NULL, check = TRUE)

`profits`	integer vector of profits, with length greater or equal 2.
`weights`	integer vector of weights, of the same length.
`capacity`	total capacity of the knapsack, integer.
`bounds`	bounds on the multiplicity of items; can be `NULL`, `Inf`, or an integer vector.
`check`	logical; Fortran check routine enabled; cannot be turned off.

Solves the 0-1 single knapsack problem for integer profits and weights when is.null(bounds), the default. It implements the branch-and-bound algorithm described in section 2.5.2 of Martello and Toth's book “Knapsack Problems”.

With bounds an integer vector it solves the bounded knapsack problem for integer profits and weights, i.e. x_j ≤ b_j for all components. If bounds is a single integer, it will be expanded to the length of profits (and weights). It implements the transformation method (that is, transformed into an equivalent 0-1 knapsack problem) described in section 3.2 of Martello and Toth's book.

With bounds==Inf it solves the unbounded knapsack problem, that is the components x_j can get as large as possible. It implements the enumerative algorithm described in section 3.6.3 of the book “Knapsack Problems”.

A mixed bounded/unbounded knapsack problem can be formulated by mixing Inf with integers in one vector as bounds.

Problem formulation: Given a set of n items and a knapsack, with

p_j = profit of item j,

w_j = weight of item j,

c = capacity of the knapsack,

select a subset of the items, described by the 0/1 vector x, so as to

maximize z = ∑_{j=1}^n p_j x_j

subject to ∑_{j=1}^n w_j x_j ≤ c

where x_j = 0 or 1 for j = 1,…,n.

The input problem description must satisfy the following conditions:

maximum weight is smaller than the capacity
sum of all weights is greater or equal to the capacity
profits[j]/weights[j], j=1..(n-1) must be monotonically decreasing.

Vector of indices, with components only 0 or 1.

This routines do not work correctly if too many or all of the elements in the sequence profit/weight are equal instead of decreasing. Thus, it cannot be usedfor, e. g., for the subset sum problem. This will be corrected in the future.

HwB email: <hwborchers@googlemail.com>

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

Other packages implementing knapsack routines.

## Example 1
p <- c(15, 100, 90, 60, 40, 15, 10,  1)
w <- c( 2,  20, 20, 30, 40, 30, 60, 10)
cap <- 102
(is <- knapsack(p, w, cap))
# [1] 1 2 3 4 6 , capacity 102 and total profit 280

## Example 2
p <- c(70, 20, 39, 37, 7, 5, 10)
w <- c(31, 10, 20, 19, 4, 3,  6)
cap <- 50
(is <- knapsack(p, w, cap))
# [1] 1 4 , capacity 50 and total profit 107

##  Example 3: 2012 as sum of a minimal number of squares
w <- (1:44)^2; p <- w-1; p[1] <- 1
knapsack(p, w, 2012)
# 1^2 + 7^2 + 21^2 + 39^2 == 2012 # as capacity is fully eaten up.

##  Example 4: <rosettacode.org/wiki/Knapsack_problem/0-1>
K <- read.table(textConnection(
"item                   weight  value   pieces
map                       9     150     1
compass                  13      35     1
water                   153     200     2
sandwich                 50     160     2
glucose                  15      60     2
tin                      68      45     3
banana                   27      60     3
apple                    39      40     3
cheese                   23      30     1
beer                     52      10     3
suntan_cream             11      70     1
camera                   32      30     1
T-shirt                  24      15     2
trousers                 48      10     2
umbrella                 73      40     1
waterproof_trousers      42      70     1
waterproof_overclothes   43      75     1
note-case                22      80     1
sunglasses                7      20     1
towel                    18      12     2
socks                     4      50     1
book                     30      10     2"), header=TRUE, row.names="item")

ks <- knapsack(K$value, K$weight, 400)    # profit: 1030, capacity: 396
is <- sort(ks$indices)
row.names(K)[is]
#  [1] "map"                "compass"                "water"                 
#  [4] "sandwich"           "glucose"                "banana"                
#  [7] "suntan_cream"       "waterproof_trousers"    "waterproof_overclothes"
# [10] "note-case"          "sunglasses"             "socks"                 

##  Example 5: Bounded knapsack problem
ks <- knapsack(K$value, K$weight, 400, K$pieces)
                                          # profit: 1200, capacity: 385
for (i in 1:length(ks$indices))
    cat(row.names(K)[ks$indices[i]], "\t", ks$nitems[i], "\n")
# map 	 1 
# socks 	 1 
# suntan_cream 	 1 
# glucose 	 2 
# note-case 	 1 
# sandwich 	 2 
# sunglasses 	 1 
# compass 	 1 
# banana 	 3 
# waterproof_overclothes 	 1 
# waterproof_trousers 	 1 
# cheese 	 1 

##  Example 6: Unbounded knapsack
p <- c(20, 39, 52, 58, 31, 4, 5)
w <- c(15, 30, 41, 46, 25, 4, 5)
knapsack(p, w, 101, bounds = Inf)
# indices: 1 3 ; nitems: 4 1 ; profit: 132 ; capacity: 101