Bottom-Up Approach: Dynamic Programming
In the previous screen, we discussed the top-down approach to solve the knapsack problem using recursion. However, the top-down approach has the drawback of solving overlapping subproblems multiple times, resulting in repetitive calculations.
To overcome this issue, we can use the bottom-up approach with dynamic programming to solve the knapsack problem. In the bottom-up approach, we start solving subproblems from the smallest inputs and build our solution up to the largest problem size.
Here's an example implementation of the bottom-up approach to the knapsack problem using dynamic programming in C#:
xxxxxxxxxx38
}public class Knapsack{ public int BottomUpKnapsack(int[] weights, int[] values, int capacity) { int n = weights.Length; int[,] dp = new int[n + 1, capacity + 1]; // Initialize the dp table for (int i = 0; i <= n; i++) { for (int j = 0; j <= capacity; j++) { if (i == 0 || j == 0) { dp[i, j] = 0; } } } // Bottom-up calculation for (int i = 1; i <= n; i++) { for (int j = 1; j <= capacity; j++) { if (weights[i - 1] > j) { dp[i, j] = dp[i - 1, j]; } elseOUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment