library(profvis)
set.seed(42)
n <- 2000
knapsack_objects <- data.frame(
w=sample(1:4000, size = n, replace = TRUE),
v=runif(n = n, 0, 10000)
)
# greedy_knapsack
profvis({
pause(0.01)
x = knapsack_objects[1:1200,]
W = 3500
v <- 0
w <- 0
df <- transform(x, c= v/w )
df<- df[order(df$c,decreasing = TRUE),]
w8 <- vector()
j=0
Val <- vector()
elements <- vector()
while(sum(w8) <= W)
{
w8 <- append(w8,df$w[j])
Val <- append(Val,df$v[j])
j <- j+1
}
if(sum(w8)> W)
{
w8 <- head(w8,-1)
Val <- head(Val,-1)
}
Val
elements <- append(elements,which(x$w %in% w8))
results <- list("value"= sum(Val),"elements"=elements)
pause(0.01)
})
# brute_force_knapsack
profvis({
pause(0.01)
x = knapsack_objects[1:8,]
W = -3500
stopifnot(is.data.frame(x))
value <- 0
elem <-c()
for(i in 1:(2^nrow(x)-1))
{wsum <- 0
vsum <- 0
loop <-c()
binary <- intToBits(i)
for(j in 1:length(binary))
{if( binary[j] == TRUE )
{
wsum <- wsum + x[j,1]
vsum <- vsum + x[j,2]
loop <- c(loop,j)
}
}
if(vsum > value && wsum <= W)
{value<-vsum
elem<-loop}}
pause(0.01)
})
#knapsack_dynamic
profvis({
pause(0.01)
x = knapsack_objects[1:12,]
W = 2000
stopifnot(is.data.frame(x))
n <- nrow(x)
w <- x[[1]] #weights
v <- x[[2]] #values
capacity <- W #capacity of knapsack
elem <- c()
m <- matrix(0,nrow = n+1,ncol = capacity+1)
#to return the max value
for (i in 2:n){
for (j in 1:capacity){
if (j > w[i])
m[i, j] <- max(m[i-1, j-w[i]] + v[i], m[i-1, j])
else
m[i,j] <- m[i-1, j]
}
}
val <- m[i, j]
value <- round(val)
#to print the elements
while(capacity>0 && n-1>0){
if(m[n,capacity]!=m[n-1,capacity]){
elem<-c(elem,n)
capacity<-capacity-w[n]
elements <- sort(elem)
}
n<-n-1
}
pause(0.01)
}
)
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.