knapsack: The Single Knapsack Problem

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

View source: R/knapsack.R

Description

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

Usage

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

Arguments

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.

Details

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:

Value

Vector of indices, with components only 0 or 1.

Note

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.

Author(s)

HwB email: <[email protected]>

References

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
## 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

knapsack documentation built on May 31, 2017, 1:45 a.m.