0-1 Knapsack Problem

Description

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

Usage

1
knapsack(w, p, cap)

Arguments

w

vector of weights.

p

vector of profits.

cap

maximal capacity of the knapsack.

Details

knapsack solves the 0-1, or: binary, single knapsack problem by using the synamic programming approach. The problem can be formulated as:

Maximize sum(x*p) such that sum(x*w) <= cap, where x is a vector with x[i] == 0 or 1.

Value

A list with components capacity, profit, and indices.

Note

Will be replaced by a compiled version.

Author(s)

HwB email: <hwborchers@googlemail.com>

References

Papadimitriou, C. H., and K. Steiglitz (1998). Combinatorial Optimization: Algorithms and Complexity. Dover Publications 1982, 1998.

Horowitz, E., and S. Sahni (1978). Fundamentals of Computer Algorithms. Computer Science Press, Rockville, ML.

See Also

knapsack::knapsack

Examples

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
# 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(w, p, 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(w, p, cap))
# [1] 1 4 , capacity 50 and total profit 107