I've noticed a recurring pattern when students first tackle the Knapsack problem: they try to solve it using a "greedy" strategy. It feels intuitive. You figure out which item has the best value-to-weight ratio, grab that one first, and then fill the remaining space with the next best thing. In your head, it seems like the most efficient way to maximize value.

The Greedy Trap: Why "Best Value First" Fails

The problem is that the 0/1 Knapsack constraint—where you either take an item in its entirety or leave it behind—breaks the greedy logic. Let's look at a concrete example. Suppose your knapsack capacity is 10kg. You have three items:

• Item A: Value $60, Weight 10kg (Ratio: 6)
• Item B: Value $50, Weight 5kg (Ratio: 10)
• Item C: Value $50, Weight 5kg (Ratio: 10)

If you follow the greedy approach, you might see Item B and C have the best ratios. You take B, then you take C. Total value: $100. That worked! But what if Item A was Value $110 and Weight 10kg? Now Item A has a ratio of 11. Greedy tells you to take Item A immediately. Total value: $110. But wait—if you had ignored the "best" ratio and taken B and C instead, you'd still have $100. That's not a great example of failure. Let's flip it: Item A is $70, Weight 10kg. Items B and C are $50 each, Weight 6kg each. Greedy takes A ($70). But you can't fit B and C together (12kg total). In this case, greedy works. But if B and C were 5kg each, Greedy takes A ($70), while the optimal choice is B+C ($100).

The greedy approach fails because it doesn't account for the "opportunity cost" of the space used. By taking the item with the best ratio, you might be blocking a combination of smaller items that collectively provide more value.

Thinking in States and Transitions

To solve this, we stop trying to make a "best" choice at each step and instead look at the problem as a series of decisions. For every item, you have two choices: you either include it or you don't. This is where the Dynamic Programming (DP) table comes in. I like to think of the table as a cheat sheet that stores the answer to smaller versions of the problem.

We create a 2D array dp[i][w], where i represents the items we are considering and w represents the current capacity of the knapsack. The value at dp[i][w] is the maximum value we can achieve using a subset of the first i items with a weight limit of w.

The logic follows a simple rule: if the current item's weight is less than or equal to the current capacity w, the value is the maximum of two scenarios:

1. We don't take the item: the value remains the same as it was for the previous item at the same weight: dp[i-1][w].
2. We do take the item: we add the item's value to the maximum value we could get with the remaining weight: val[i-1] + dp[i-1][w - wt[i-1]].

Translating the Logic into C

In C, we have to be careful about how we allocate this table. For a small exercise, a stack-allocated 2D array is fine, but in a production environment, you'd likely use malloc to handle larger datasets. Here is the structural pattern I recommend using for the implementation:

int knapsack(int W, int wt[], int val[], int n) {
    int i, w;
    int dp[n + 1][W + 1];

    for (i = 0; i <= n; i++) {
        for (w = 0; w <= W; w++) {
            if (i == 0 || w == 0) {
                dp[i][w] = 0;
            } else if (wt[i - 1] <= w) {
                // Max of (taking the item) vs (leaving the item)
                int take = val[i - 1] + dp[i - 1][w - wt[i - 1]];
                int leave = dp[i - 1][w];
                dp[i][w] = (take > leave) ? take : leave;
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
    return dp[n][W];
}

Notice how the loops build the solution from the ground up. We solve for a knapsack of size 0, then size 1, then size 2, and so on. By the time we reach dp[n][W], we've already calculated every possible sub-combination required to find the absolute maximum.

📋 Practical Task

Exercise: Implementing the Treasure Haul Optimizer

You are writing a program for a treasure hunter who has a knapsack with a fixed weight capacity. You are given a set of items, each with a weight and a value. Your goal is to implement the knapsack function using Dynamic Programming to return the maximum value possible.

Complete the code below. Ensure your solution handles the case where an item is too heavy to fit into the current sub-capacity of the knapsack.

#include <stdio.h>

// TODO: Implement the knapsack function
int knapsack(int W, int wt[], int val[], int n) {
    // Your implementation here
}

int main() {
    int values[] = {60, 100, 120};
    int weights[] = {10, 20, 30};
    int W = 50;
    int n = sizeof(values) / sizeof(values[0]);
    
    int max_val = knapsack(W, weights, values, n);
    printf("Maximum value in Knapsack = %d\n", max_val);
    
    // Expected Output: Maximum value in Knapsack = 220
    return 0;
}