배낭 0-1 in R

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

w 무게의 벡터이다 패키지 아다지오의 knapsack 기능을 살펴 갖는 것은 당신을 도움이 될 것입니다

, p 이익의 벡터와 cap은 k입니다.

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)에 사용되는 모든 개체를 선언하지 않았을 것 같다 (?knapsack 참조) : 당신은 또한 그들을 선언해야 함수의 매개 변수로 사용하십시오.

2. F 함수 이름은 함수 내부에서 호출됩니다. 따라서 (i==0 | k==0)은 결코 사실 일 수 없으므로 함수는 결코 처리를 중지하지 않습니다.