DSA Cprogramming

0 1 Knapsack Problem in DSA C

Choose your learning style10 modes available

Learn Why Deep Visual Try Challenge Project Recall Time

Mental Model

Choose items one by one to maximize value without exceeding weight limit, but you can only take each item once.

Analogy: Imagine packing a backpack for a trip with limited space. You pick items to get the most useful stuff without overloading the bag.

Knapsack capacity: 5
Items: [weight, value]
[1, 6], [2, 10], [3, 12]
Backpack: capacity 5 -> can hold items up to total weight 5

Dry Run Walkthrough

Input: items: [(weight=1, value=6), (weight=2, value=10), (weight=3, value=12)], capacity=5

Goal: Find the maximum value we can carry without exceeding capacity 5

Step 1: Consider first item (weight=1, value=6), update dp for capacities 1 to 5

dp array after step 1: [0, 6, 6, 6, 6, 6]

Why: We can take the first item if capacity allows, so value 6 is possible from capacity 1 upwards

Step 2: Consider second item (weight=2, value=10), update dp for capacities 2 to 5

dp array after step 2: [0, 6, 10, 16, 16, 16]

Why: At capacity 2, taking second item gives value 10 better than previous 6; at capacity 3, combine first and second items for value 16

Step 3: Consider third item (weight=3, value=12), update dp for capacities 3 to 5

dp array after step 3: [0, 6, 10, 16, 18, 22]

Why: At capacity 4, taking third item plus first item gives 18; at capacity 5, taking third and second items gives max value 22

Result:

dp array final: [0, 6, 10, 16, 18, 22]
Maximum value: 22

Annotated Code

DSA C

#include <stdio.h>

// Function to find max of two integers
int max(int a, int b) {
    return (a > b) ? a : b;
}

// 0 1 Knapsack function
int knapsack(int capacity, int weights[], int values[], int n) {
    int dp[capacity + 1];
    for (int i = 0; i <= capacity; i++) {
        dp[i] = 0; // initialize dp array with 0
    }

    // For each item
    for (int i = 0; i < n; i++) {
        // Traverse capacities from high to low to avoid reuse of same item
        for (int w = capacity; w >= weights[i]; w--) {
            // Update dp[w] if including item i gives better value
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    return dp[capacity];
}

int main() {
    int weights[] = {1, 2, 3};
    int values[] = {6, 10, 12};
    int capacity = 5;
    int n = sizeof(weights) / sizeof(weights[0]);

    int max_value = knapsack(capacity, weights, values, n);
    printf("Maximum value: %d\n", max_value);
    return 0;
}

for (int i = 0; i < n; i++) {

iterate over each item to consider including it

for (int w = capacity; w >= weights[i]; w--) {

iterate backwards over capacities to avoid reusing the same item multiple times

dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);

update dp[w] to max of excluding or including current item

OutputSuccess

Maximum value: 22

Complexity Analysis

Time: O(n * capacity) because we process each item for each capacity up to the limit

Space: O(capacity) because we use a one-dimensional dp array of size capacity+1

vs Alternative: Compared to a 2D dp approach with O(n * capacity) time and space, this optimized 1D dp reduces space to O(capacity)

Edge Cases

capacity is zero

maximum value is zero since no items can be taken

DSA C

for (int i = 0; i <= capacity; i++) { dp[i] = 0; }

no items (n=0)

maximum value is zero because no items to choose

DSA C

for (int i = 0; i < n; i++) { ... }

items heavier than capacity

those items are never included as weights[i] > capacity prevents dp update

DSA C

for (int w = capacity; w >= weights[i]; w--) { ... }

When to Use This Pattern

When you need to pick items with weights and values to maximize value without exceeding capacity, and each item can be chosen once, use the 0 1 Knapsack pattern with dynamic programming.

Common Mistakes

Mistake: Iterating capacities from low to high causing reuse of the same item multiple times
Fix: Iterate capacities from high to low to ensure each item is only counted once

Mistake: Using 2D dp without space optimization when 1D dp suffices
Fix: Use 1D dp array and iterate capacities backwards to optimize space

Summary

Find the maximum total value of items that fit in a knapsack without exceeding its capacity, choosing each item at most once.

Use when you have a set of items with weights and values and want to maximize value under a weight limit with no repeats.

The key is to build up solutions for smaller capacities and items, updating from high to low capacity to avoid reusing items.

Practice

(1/5)

1. In the 0/1 Knapsack problem, why can't we take fractions of items like in the Fractional Knapsack?

easy

A. Because the DP table only stores integers

B. Because each item must be taken as a whole unit or not at all - fractional inclusion violates the problem definition

C. Because fractions make the recursion infinite

D. Because the weight array only accepts integer values

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

0 1 Knapsack Problem in DSA C

Practice

Solution

0/1 Constraint

Why Greedy Fails

Why DP is Needed

Final Answer:

Solution

Table Dimensions

Why +1

In C

Final Answer:

Solution

Can't Include Overweight Item

Inherit from Previous Row

Full Recurrence

Final Answer:

Solution

Time Complexity

Space Complexity

Note

Final Answer:

Solution

Problem With Left-to-Right

Right-to-Left Prevents Reuse

0/1 vs Unbounded

Final Answer:

Ready to prove it?