Knapsack 0-1 in R

Question

J'ai essayé de formuler un problème de sac à dos simple, mais je ne vois pas pourquoi cela ne fonctionne pas.

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

Avoir un regard sur la fonction knapsack du paquet adagio devrait vous aider, où w est le vecteur de poids, p le vecteur des bénéfices et cap est votre k. (Voir ?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)) 
} 

Cependant, les problèmes de votre fonction semblent être

1. Vous n'avez pas fait tous les objets utilisés dans votre fonction (w et v): vous devez également les déclarer en tant que paramètres de votre fonction.

2. F Le nom de votre fonction est appelé dans votre fonction. Par conséquent, comme (i==0 | k==0) ne pourrait jamais être vrai, la fonction n'arrêtera jamais le traitement.