subsetsum: The Subset Sum Problem

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

View source: R/subsetsum.R

Description

Solves the subset sum problem for integers.

Usage

1
subsetsum(weights, target, check = TRUE, core = 5000)

Arguments

weights

integer vector of weights.

target

target sum to be reached, integer.

check

logical; Fortran check routine enabled; cannot be turned off.

core

length of dynamic programming list; internal parameter.

Details

Solves the subset sum problem for integer weights. It implements the mixed algorithm described in section 4.2.3 of the book“Knapsack Problems” by S. Martello and P. Toth.

The subset sum problem can be described as follows: Given integer weights w[j], j=1,...,n and a target value W, find a subset of weights, defined by a 0-1 vector x[j], such that

Maximize Z = w[1]*x[1] + ... + w[n]*x[n]

subject to: w[1]*x[1] + ... + w[n]*x[n] <= W

The input problem description must satisfy the following conditions:

Value

A list with ssum the maximal summation reached, and inds the indices of weights.

Author(s)

HwB email: <[email protected]>

The Fortran routines used are copyright of S. Martello and P. Toth and are distributed under a free license only for personal research and academic use.

References

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

See Also

adagio::subsetsum

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
##  Example from R-help
amount <- 4748652
products <- c(
    1198000, 1110000, 1031655, 829350, 800000, 533600, 456000, 123289,
      90900,   83800,   80000,  77382,  77000,  76950,  71190,  71040,
      70740,   70740,   63051,  59700,  59500,  55000,  53730,  51186,
      49600,   48048,   42000,  42000,  42000,  42000,  42000,  42000,
      42000,   42000,   42000,  42000,  40000,  35100,  35000,  33000,
      33000,   30500,   30500,  30500,  30500,  28000,  28000,  28000,
      28000,   28000,   27465,  27000,  27000,  27000,  27000,  27000,
      27000,   26140,   25908,  21716,  15025,  15025,  15025,  15025)
# find a subset that sums up to amount:
R <- subsetsum(products, amount)
R$ssum == amount            # TRUE
R$inds                      # 1  2  3  4  8  9 10 12 24 25 40 46 51 64

##  Some weights are greater than the target
n <- length(products)
amount <- 1000000
imax <- which(products > amount)
prods <- products[products <= amount]

# reproduce the indices
R <- subsetsum(prods, amount)
inds <- setdiff(1:n, imax)[R$inds]              # 4 25 39 47 49 61 64
sum(products[inds]) == amount                   # TRUE

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