memory optimization of Unbounded knapsack algorithm

Question

In the classic unbounded knapsack algorithm solution using Dynamic Programming (https://en.wikipedia.org/wiki/Knapsack_problem#Unbounded_knapsack_problem), we allocate an integer array of size of knapsack to store the max values.

If I have a knapsack with a 1 Billion size, how do I optimize the DP solution to make sure that I can accommodate the int[] knapsack array? Because the memory taken by Java for 1B sized knapsack = 10^9 * 4Bytes = 3.7GB of memory alone.

Answer 1

Instead of trying to solve this problem with all of the data in memory, you'll have to work out a solution that uses secondary memory such as accessing a file or possibly setup a database.