#### Documented in knapsack_dynamic

```#' @title Knapsack Dynamic Algorithm
#' @name knapsack_dynamic
#' @param x A data frame with numeric positive values.
#' @param W A positive numeric scalar.
#' @return A list with maximum value and elements.
#' @description The knapsack problem is a problem in combinatorial optimization: how to maximasiethe value of fitted object by fullfilling the weight constraint.
#' @references \url{https://en.wikipedia.org/wiki/Knapsack_problem}
#' @export

knapsack_dynamic <- function(x, W) {

stopifnot(is.data.frame(x),
apply(x, c(1, 2), is.numeric),
is.numeric(W))

stopifnot(x > 0,
length(W) == 1,
W > 0)

# initiate variables
n <- nrow(x)
K <-
matrix(rep.int(0, (n + 1) * (W + 1)), ncol = W + 1, nrow = n + 1)
# save the initial order of the elements
element_order <- order(x[, 1])
# sort weights and values in ascending order
wt <- x[order(x[, 1]), 1]
val <- x[order(x[, 1]), 2]
elements <- c()

for (i in 1:(n + 1)) {
# This solution produces matrix with [1,] and [,1] filled with 0s.
# Hence, the row number is n+1 and column number is W+1
for (w in 1:(W + 1)) {
if (i == 1 || w == 1) {
K[i, w] <- 0
}
else if (wt[i - 1] < w - 1) {
K[i, w] <- max(val[i - 1] + K[i - 1, w - wt[i - 1]],  K[i - 1, w])
}
else if (wt[i - 1] == w - 1) {
K[i, w] <- max(val[i - 1] + 0,  K[i - 1, w])
}
else{
K[i, w] <- K[i - 1, w]
}

}
}

# Trace back which elements were included
# Initiate the variables
j <- n + 1
k <- W + 1
i <- 1

while (j >= 2 && k >= 1) {
if (K[j, k] > K[j - 1, k]) {
elements[i] <- element_order[j - 1]
i <- i + 1
k <- k - wt[j - 1]
}
# move one row up in the result matrix
j <- j - 1
}

# Sort chosen items in ascending order
items <- elements[order(elements)]
result <-
list(value = round(K[n + 1, W + 1], 0), elements = items)
return(result)
}
```
poceviciute/AdvRprogr_lab6 documentation built on Oct. 6, 2017, 3:21 a.m.