Space Optimization: Rolling Arrays
In the previous screen, we discussed the dynamic programming approach to solve the Knapsack Problem using a bottom-up approach. However, this implementation can consume a large amount of memory, especially when the number of items and the capacity of the knapsack are both large.
To optimize the space usage in the bottom-up implementation, we can make use of rolling arrays. Instead of using a 2D array to store the values of the subproblems, we can use two 1D arrays and alternate between them.
Here's an example implementation of the Knapsack Problem using space optimization and rolling arrays in C#:
xxxxxxxxxx30
}public class Knapsack{ public float SolveKnapsack(int[] weights, int[] values, int capacity) { int n = weights.Length; float[,] dp = new float[2, capacity + 1]; int currRow = 1; int prevRow = 0; for (int i = 0; i < n; i++) { currRow = i % 2; prevRow = (i + 1) % 2; for (int j = 1; j <= capacity; j++) { if (weights[i] <= j) { dp[currRow, j] = Math.Max(dp[prevRow, j], values[i] + dp[prevRow, j - weights[i]]); } else { dp[currRow, j] = dp[prevRow, j]; } } } return dp[currRow, capacity]; }OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment