Top-Down Approach: Recursive Solution

In the top-down approach, we solve the knapsack problem by breaking it down into subproblems and solving each subproblem recursively.

To implement the top-down approach, we can use a recursive function that takes the current capacity of the knapsack and the current item index as parameters. The base case of the recursion is when we have either considered all the items or when the knapsack capacity is 0.

In each recursive call, we have two choices:

1. Include the current item: If the weight of the current item is less than or equal to the remaining capacity of the knapsack, we can include it and recursively solve the subproblem with the remaining capacity and the next item index.

   TEXT/X-CSHARP

   1int include = values[index] + RecursiveHelper(weights, values, capacity - weights[index], index - 1);

2. Exclude the current item: If the weight of the current item is greater than the remaining capacity of the knapsack, we exclude it and recursively solve the subproblem with the same capacity and the next item index.

   TEXT/X-CSHARP

   1int exclude = RecursiveHelper(weights, values, capacity, index - 1);

Finally, we return the maximum value among the two choices as the result of the recursive call.

Here's an example implementation in C#:

xxxxxxxxxx

public class Knapsack

{

    public int RecursiveKnapsack(int[] weights, int[] values, int capacity)

    {

        int n = weights.Length;

        return RecursiveHelper(weights, values, capacity, n - 1);

    }

​

    private int RecursiveHelper(int[] weights, int[] values, int capacity, int index)

    {

        // Base case: no items or no capacity

        if (index < 0 || capacity == 0)

            return 0;

​

        // If the current item's weight exceeds the capacity

        // exclude it from the knapsack

        if (weights[index] > capacity)

            return RecursiveHelper(weights, values, capacity, index - 1);

​

        // Recursive calls to either include or exclude the current item

        int include = values[index] + RecursiveHelper(weights, values, capacity - weights[index], index - 1);

        int exclude = RecursiveHelper(weights, values, capacity, index - 1);

​

        // Return the maximum value

        return Math.Max(include, exclude);

    }

}