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

1 | ```
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`

.

A list with components `capacity`

, `profit`

, and `indices`

.

Will be replaced by a compiled version.

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.

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
``` |

Questions? Problems? Suggestions? Tweet to @rdrrHQ or email at ian@mutexlabs.com.

Please suggest features or report bugs with the GitHub issue tracker.

All documentation is copyright its authors; we didn't write any of that.