R中的背包0-1

Question

我一直在试图制定一个简单的背包问题，但我看不出为什么它不起作用。

i <- c(1,2,3,4) 
v <- c(100,80,10,120) 
w <- c(10,5,10,4) 
k <- 15 

F <- function(i,k){ 
    if (i==0 | k==0){ 
    output <- 0 
    } else if (k<w[i]){ 
    output <- F(i-1,w) 
    } else { 
    output <- max(v[i]+ F(i-1, k-w[i]), F(i-1,k)) 
    } 
    return(output) 
} 

Answer 1

在看看包装慢板的knapsack功能应该可以帮助你，在这里w是权重向量，p利润的载体和cap是你k。 （见?knapsack）

knapsack <- 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) 
    } 
    fmax <- G[cap + 1, 1] 
    f <- fmax 
    j <- cap + 1 
    for (k in n:1) { 
     if (F[j, k] < f) { 
      x[k] <- TRUE 
      j <- j - w[k] 
      f <- F[j, k] 
     } 
    } 
    inds <- which(x) 
    wght <- sum(w[inds]) 
    prof <- sum(p[inds]) 
    return(list(capacity = wght, profit = prof, indices = inds)) 
} 

然而，在你的函数的问题似乎是

1. 你没有申报在你的函数（w和v）所使用的所有对象：你也应该申报他们作为你的函数的参数。

2. F这是您的函数的名称在您的函数内部调用。因此，由于(i==0 | k==0)永远不会成立，函数永远不会停止处理。