In this article we are going to discuss the integer knapsack problem. It is dynamic programming related problem in computer science. First of all, let’s consider the problem itself. Given weights and values of n items. Put these items into a knapsack of capacity W to get total value in the knapsack. The brute-force solution is to consider all subsets of items and calculate the total weight and value of all subsets. From all such subsets, find the maximum value subset where the total weight is smaller than W. Of course this is a very slow approach, because the number of possible subsets is enormous.
Dynamic programming approach
So better approach is to use dynamic programming for solving the integer knapsack problem. Let’s take advantage of the overlapping subproblems. We have to consider several subproblems. What would be the optimal solution to the problem if W=0? What would be the optimal solution if W=1? And so on. We have to do the same with the items. What would be the optimal solution if we have just 1 item? What would be the optimal solution if we have the first 2 items? And so on. So we have to construct a dynamic programming table: it stores the subsolutions for these subproblems. Then we can combine these subsolutions in the final solution. I can tell you, the implementation of integer knapsack problem in java quite easily.
This is how you implement integer knapsack problem in java!