# knapsack: 0-1 Knapsack Problem In adagio: Discrete and Global Optimization Routines

## Description

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

## Usage

 `1` ```knapsack(w, p, cap) ```

## Arguments

 `w` integer vector of weights. `p` integer vector of profits. `cap` maximal capacity of the knapsack, integer too.

## Details

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

## Value

A list with components `capacity`, `profit`, and `indices`.

## Note

Will be replaced by a compiled version.

## Author(s)

HwB email: <[email protected]>

## 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.

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

### Example output

```\$capacity
[1] 102

\$profit
[1] 280

\$indices
[1] 1 2 3 4 6

\$capacity
[1] 50

\$profit
[1] 107

\$indices
[1] 1 4
```

adagio documentation built on May 17, 2018, 3:01 a.m.