Optimal Solution of Minmax 0/1 Knapsack Problem using Dynamic Programming

Abstract

Knapsack problem is a problem that occurs when looking for optimal selection of objects that will be put into a container with limited space and capacity. On the issue of loading goods into the container, optimal selection of objects or items to be sent must fulfilled to minimize the total weight of the capacity or volume limits without exceeding the maximum capacity of containers that have been determined. The types of knapsack that has been discussed so far is only to maximize the use not to exceed the limits specified capacity so it cannot be applied to the problem. This study aims to develop a dynamic programming algorithm to solve the MinMax 0/1 knapsack, which is an extension of the 0/1 knapsack with minimal and maximal constrain.  The result study showed that application of the MinMax 0/1 knapsack is used to generate the optimal solution to the problem of loading system goods into the container to optimize container space available compared with the loading of goods by PT DFI.

DOI: http://dx.doi.org/10.11591/ij-ict.v2i1.1299