this excerpt cran documentation adagio function knapsack() functions expected -- solves knapsack problem profit vector p, weight vector w, , capacity cap, selecting subset of elements maximum profit subject constraint total weight of selected elements not exceed capacity.
library(adagio) p <- c(15, 100, 90, 60, 40, 15, 10, 1) w <- c( 2, 20, 20, 30, 40, 30, 60, 10) cap <- 102 (is <- knapsack(w, p, cap)) how can add vector length constraint solution , still optimal answer? example, above exercise, selected subset must include 3 elements.
one approach explicitly model problem mixed integer linear programming problem; advantage of explicitly modeling in way linear constraints "pick 3 objects" simple model. here example lpsolve package in r, each element in knapsack problem represented binary variable in mixed integer linear programming formulation. requirement select 3 elements captured constraint requiring decision variables sum 3.
library(lpsolve) p <- c(15, 100, 90, 60, 40, 15, 10, 1) w <- c( 2, 20, 20, 30, 40, 30, 60, 10) cap <- 102 exact.num.elt <- 3 mod <- lp(direction = "max", objective.in = p, const.mat = rbind(w, rep(1, length(p))), const.dir = c("<=", "="), const.rhs = c(cap, exact.num.elt), all.bin = true) # solution which(mod$solution >= 0.999) # [1] 2 3 4 # profit mod$objval # [1] 250 while subsetting optimal solution adagio:::knapsack function desired size reasonable heuristic case when desired subset size smaller cardinality of optimal solution standard problem, there exist examples optimal solution standard knapsack problem , optimal solution size-constrained knapsack problem disjoint. instance, consider following problem data:
p <- c(2, 2, 2, 2, 3, 3) w <- c(1, 1, 1, 1, 2, 2) cap <- 4 exact.num.elt <- 2 with capacity 4 , no size constraint, standard knapsack problem select 4 elements profit 2 , weight 1, getting total profit 8. however, size limit 2 optimal solution instead select 2 elements profit 3 , weight 2, getting total profit 6.
Comments
Post a Comment