Greedy solution method for knapsack problems with R

Abstract

The Knapsack problems contained in integer programming are one of the combinatoral optimization methods that maximize utility without exceeding the capacity. Different methods have been developed for the solution of Knapsack problems. In this study, Branch boundary algorithm, Balas algorithm and Greedy algorithm are used. Among these, R program code was developed for Greedy algorithm and sample problems were solved in different models. Results were also obtained using the pomQM package program for 3, 5, 7, 10, 30 and 50 variables. All results were compared using the developed R code. The objective function values, constraint values and capacity values of the problems are produced by random in R program. Even when the number of variables for single and two-dimensional, pure (0-1) binary problems is large, it can be obtained optimal or close to optimality results with Greedy method. As a result, R-code was developed without any problem of size and number of constraints.