0 1 Knapsack Problem in DSA C - Build from Scratch

0 1 Knapsack Problem

📖 Scenario: You are packing a backpack for a hiking trip. You have a list of items, each with a weight and a value. Your backpack can only carry a limited weight. You want to choose items to maximize the total value without exceeding the weight limit.

🎯 Goal: Build a program that uses the 0 1 Knapsack algorithm to find the maximum value of items that fit in the backpack without exceeding the weight limit.

📋 What You'll Learn

Create arrays for item weights and values

Create an integer variable for the maximum weight capacity

Implement the 0 1 Knapsack dynamic programming logic

Print the maximum value that fits in the backpack

💡 Why This Matters

🌍 Real World

Packing efficiently for trips, resource allocation, budget management, and many optimization problems use the 0 1 Knapsack approach.

💼 Career

Understanding dynamic programming and optimization algorithms is important for software engineering, data science, and technical interviews.

1

Create arrays for item weights and values

Create two integer arrays called weights and values with these exact values: weights = {2, 3, 4, 5} and values = {3, 4, 5, 6}.

DSA C

# Your code here

Hint

Use curly braces to initialize arrays with the exact values given.

2

Create a variable for maximum weight capacity

Create an integer variable called maxWeight and set it to 5.

DSA C

int weights[] = {2, 3, 4, 5};
int values[] = {3, 4, 5, 6};
// Your code here

Hint

Use int maxWeight = 5; to set the backpack's weight limit.

3

Implement the 0 1 Knapsack dynamic programming logic

Create an integer variable n for the number of items using sizeof(weights) / sizeof(weights[0]). Then create a 2D integer array dp of size (n+1) x (maxWeight+1). Use nested for loops with variables i and w to fill dp using the 0 1 Knapsack logic: if the current item's weight is less than or equal to w, set dp[i][w] to the maximum of including or excluding the item; otherwise, exclude the item.

DSA C

int weights[] = {2, 3, 4, 5};
int values[] = {3, 4, 5, 6};
int maxWeight = 5;
// Your code here

Hint

Use two loops: outer loop for items i, inner loop for weights w. Initialize dp[i][w] to 0 when i or w is 0.

4

Print the maximum value that fits in the backpack

Use printf to print the maximum value stored in dp[n][maxWeight] with the exact format: "Maximum value: %d\n".

DSA C

int weights[] = {2, 3, 4, 5};
int values[] = {3, 4, 5, 6};
int maxWeight = 5;

int n = sizeof(weights) / sizeof(weights[0]);
int dp[n+1][maxWeight+1];

for (int i = 0; i  exclude) ? include : exclude;
        } else {
            dp[i][w] = dp[i-1][w];
        }
    }
}
// Your code here

Hint

Print the value in dp[n][maxWeight] using printf("Maximum value: %d\n", dp[n][maxWeight]);.