0-1背包问题：C#自顶向下递归动态规划实现求助

Hey there! Nice work getting the naive recursive solution up and running correctly. The next step to optimize it is adding memoization—this will store results of subproblems we've already solved, so we don't waste time recalculating them over and over. Here's a step-by-step guide to converting your code:

Core Idea #

The naive recursive approach recalculates the same Knapsack(i, w) subproblems hundreds (or thousands) of times. A memoization table (a 2D array here) will keep track of computed results: when we encounter a subproblem we've already solved, we just return the stored value instead of recursing again.

Modified Code with Memoization #

First, let's fix the small typo (objWert → objValue) and add the memoization logic:

static int[] objValue;
static int[] objWeight;
static int[,] memo; // Memoization table to store computed subproblem results

static void Main(string[] args) {
    objValue = new int[] { 0, 11, 8, 4, 12, 4, 6, 9, 10 };
    objWeight = new int[] { 0, 4, 2, 2, 5, 6, 3, 5, 7 };
    int objNumber = objValue.Length - 1; // Fixed typo here
    int maxWeight = 12;
    
    // Initialize memo table with -1 (marks unsolved subproblems)
    memo = new int[objNumber + 1, maxWeight + 1];
    for (int i = 0; i <= objNumber; i++) {
        for (int w = 0; w <= maxWeight; w++) {
            memo[i, w] = -1;
        }
    }
    
    Console.WriteLine(Knapsack(objNumber, maxWeight));
    Console.ReadLine();
}

public static int Knapsack(int i, int w) {
    // Base case: no items left or no weight capacity
    if (i == 0 || w == 0) {
        return 0;
    }
    
    // Check if we've already solved this subproblem
    if (memo[i, w] != -1) {
        return memo[i, w];
    }
    
    int result;
    if (objWeight[i] > w) {
        // Can't take the i-th item, recurse on the rest
        result = Knapsack(i - 1, w);
    } else {
        // Choose between taking or not taking the i-th item
        int case1 = Knapsack(i - 1, w); // Don't take
        int case2 = objValue[i] + Knapsack(i - 1, w - objWeight[i]); // Take
        result = Math.Max(case1, case2);
    }
    
    // Store the result in memo before returning
    memo[i, w] = result;
    return result;
}

Key Changes Explained #

• Memoization Table: We added a 2D array memo where memo[i, w] holds the maximum value for the first i items with a weight limit of w. Initializing all values to -1 lets us easily check if a subproblem is unsolved.
• Check Before Recursion: In the Knapsack method, we first check if memo[i, w] is not -1—if so, we return the stored value immediately.
• Store Results: After computing the result for a subproblem, we save it to memo[i, w] so future calls can reuse it.
• Typo Fix: Changed objWert.Count() to objValue.Length (since arrays use Length, not Count(), and objWert was a typo for objValue).

Why This Works #

The naive recursive solution has a time complexity of O(2ⁿ) (exponential), which gets very slow as the number of items increases. With memoization, we reduce this to O(n*W) (linear in the number of items multiplied by the max weight), which is much more efficient for larger inputs. The result will be exactly the same as your original code—just faster!

内容的提问来源于stack exchange，提问作者DerBenutzer