R/dynamic_knapsack.R

In abhi-vellala/732A94lab6: Knapsack Problem Algorithms

#'@title Dynamic Knapsack Algorithm
#'@description Solution to the knapsack problem using Dynamic Programming.\cr
#'The algorithm solves the knapsack problem exact by iterating over all possible values of weight.
#'@references \href{https://en.wikipedia.org/wiki/Knapsack_problem#0.2F1\%20knapsack\%20problem}{Wikipedia}
#'@param x Dataframe with variables v and w.
#'@param W Integer. Size of the knapsack.
#'@export
#'@aliases kdp
#'@return Returns a list with the total final value and the items added to the knapsack.

dynamic_knapsack <- function(x,W){
	
	num_distinct_items <- sum(!duplicated(x))
	m <- matrix(0,nrow=nrow(x)+1 , ncol=W+1 )
	
	for(i in 1:nrow(x)){
		for(j in 1:W+1){
			if(x$w[i]>j){
				m[i+1,j] <- m[i,j]
			}
			else{
				m[i+1,j] <- max( m[i,j] , m[i,j-x$w[i]] + x$v[i] )
			}
		}
	}
	
	output_table<-list("value"=0,"elements"=c())
	output_table$value=round(m[nrow(m),ncol(m)])
	
	items <- c()
	r <- nrow(x)+1
	c <- W+1
	while( r>1 ){
		if( m[r-1,c] < m[r,c] ){
			items <- append(items, r-1)
			r <- r - 1
			c <- c - x$w[r]
		}else{
			r <- r-1
		}
	}
	output_table$elements = sort(items,decreasing = FALSE)
	
	return(output_table)
}

# Setup:
# set.seed(42)
# n <- 2000
# knapsack_objects <- data.frame(w=sample(1:4000, size = n, replace = TRUE), v=runif(n = n, 0, 10000))

# How much time does it takes to run the algorithm for n = 500 objects? 22.56474 seconds
# start_time <- Sys.time()
# dynamic_knapsack(x = knapsack_objects[1:500,], W = 3500) # 22160 , 3 8 14
# end_time <- Sys.time()
# cat("Runtime for 500 objects: ",end_time-start_time,"\n")

# Execution examples:
# dynamic_knapsack(x = knapsack_objects[1:8,], W = 3500) # 16770 , 5 8
# dynamic_knapsack(x = knapsack_objects[1:12,], W = 3500) # 16770 , 5 8
# dynamic_knapsack(x = knapsack_objects[1:8,], W = 2000) # 15428 , 3 8
# dynamic_knapsack(x = knapsack_objects[1:12,], W = 2000) # 15428 , 3 8