CODEWITHSUNDEEP
rmathematical-optimizationknapsack-problem
Liz Young
Liz Young

Reputation: 408

knapsack() vector length issues

When I run

weights <- 1:50
profits <- 1:50
library(adagio)
knapsack(w = weights, p = profits, cap = 30)

I get the error

Error in F[, k] <- G : 
  number of items to replace is not a multiple of replacement length
In addition: Warning message:
In pmax(G, H) : an argument will be fractionally recycled

but when I run smaller sized vectors, like

weights <- 1:20
profits <- 1:20
knapsack(w = weights, p = profits, cap = 30)

it runs fine. Does knapsack() just slow down (and prevent running) for larger sets? I'm looking to use lengths in the thousands eventually.

Upvotes: 2

Views: 305

Answers (2)

Ralph
Ralph

Reputation: 265

I received the same error (which is how I got this SO post..) I think that the adagio knapsack function doesn't like profits or weights that are fractional values. I used rnorm() to generate profits and weights, to compare their results to another knapsack function that I personally wrote. Even with a capacity that was several times larger than all the weights put together, I was getting the 'recycling' error. However when I rounded off the rnorm() vectors before passing them as arguments to knapsack, no problems.

Upvotes: 1

josliber
josliber

Reputation: 44330

This is an issue with passing elements with weight exceeding the total capacity. To see the issue, let's look at the first few lines of the knapsack function:

function (w, p, cap) 
{
    n <- length(w)
    x <- logical(n)
    F <- matrix(0, nrow = cap + 1, ncol = n)
    G <- matrix(0, nrow = cap + 1, ncol = 1)
    for (k in 1:n) {
        F[, k] <- G
        H <- c(numeric(w[k]), G[1:(cap + 1 - w[k]), 1] + p[k])
        G <- pmax(G, H)
    }

When iteratively filling the F matrix one column at a time, the algorithm creates a vector H with the following command (and then immediately computing pmax(G, H)):

H <- c(numeric(w[k]), G[1:(cap + 1 - w[k]), 1] + p[k])

numeric(w[k]) has length w[k], and when w[k] <= cap, G[1:(cap + 1 - w[k]), 1] + p[k] has length cap + 1 - w[k], meaning the entire vector H has length cap+1, matching the size of G. On the other hand, when w[k] == cap + 1 we will end up with an H vector of size cap+2, which doesn't match the size of G and gives us trouble, and with w[k] > cap + 1 we will get an error for mixing positive and negative indices.

Getting back to your example function call, you have weights up to 50 but only a capacity of 30, yielding an error:

weights <- 1:50
profits <- 1:50
knapsack(w = weights, p = profits, cap = 30)
# Error in F[, k] <- G : 
#   number of items to replace is not a multiple of replacement length
# In addition: Warning message:
# In pmax(G, H) : an argument will be fractionally recycled

However when you limit to elements with weight not exceeding the capacity, you get no errors:

knapsack(w = weights[weights <= 30], p = profits[weights <= 30], cap = 30)
# $capacity
# [1] 30
# 
# $profit
# [1] 30
# 
# $indices
# [1] 1 2 3 4 5 7 8

It would be most ideal if the knapsack function gracefully removed any object with weight exceeding the capacity (since no such elements could ever be used in a feasible solution) and gave you a solution for the code you posted, but as a workaround you could simply remove them yourself from the input to the knapsack function.

Upvotes: 2

Related Questions