knapsack | R Documentation |

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

knapsack(w, p, cap)

`w` |
integer vector of weights. |

`p` |
integer vector of profits. |

`cap` |
maximal capacity of the knapsack, integer too. |

`knapsack`

solves the 0-1, or: binary, single knapsack problem by
using the dynamic 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`

.

Knapsack procedures can even solve subset sum problems, see the examples 3 and 3' below.

A list with components `capacity`

, `profit`

, and `indices`

.

HwB email: <hwborchers@googlemail.com>

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.

`knapsack::knapsack`

# 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 ## Not run: ## Example 3: subset sum p <- seq(2, 44, by = 2)^2 w <- p is <- knapsack(w, p, 2012) p[is$indices] # 16 36 64 144 196 256 324 400 576 ## Example 3': maximize number of items # w <- seq(2, 44, by = 2)^2 # p <- numeric(22) + 1 # is <- knapsack(w, p, 2012) ## Example 4 from Rosetta Code: w = c( 9, 13, 153, 50, 15, 68, 27, 39, 23, 52, 11, 32, 24, 48, 73, 42, 43, 22, 7, 18, 4, 30) p = c(150, 35, 200, 160, 60, 45, 60, 40, 30, 10, 70, 30, 15, 10, 40, 70, 75, 80, 20, 12, 50, 10) cap = 400 system.time(is <- knapsack(w, p, cap)) # 0.001 sec ## End(Not run)

Embedding an R snippet on your website

Add the following code to your website.

For more information on customizing the embed code, read Embedding Snippets.