DP vs Recursion vs Greedy Choosing the Right Tool in DSA C - Build Both Approaches

DP vs Recursion vs Greedy Choosing the Right Tool

📖 Scenario: Imagine you are helping a small delivery company decide the best way to pack their trucks with packages. Each package has a weight and a value. The company wants to maximize the total value of packages in the truck without exceeding the weight limit.There are three ways to solve this problem: simple recursion, dynamic programming, and a greedy approach. You will learn how to set up the data, configure the problem, apply each method, and see the results.

🎯 Goal: Build a program that uses recursion, dynamic programming, and greedy methods to solve the package packing problem. You will compare their outputs to understand which method works best for this problem.

📋 What You'll Learn

Create an array of package weights and values

Set a maximum weight limit for the truck

Implement a recursive function to find max value

Implement a dynamic programming solution for max value

Implement a greedy approach based on value-to-weight ratio

Print the results of all three methods

💡 Why This Matters

🌍 Real World

Delivery companies and logistics use these methods to pack trucks efficiently, saving fuel and time.

💼 Career

Understanding these approaches helps in roles like software engineering, data analysis, and operations research where optimization problems are common.

1

Create package data arrays

Create two arrays called weights and values with these exact values: weights = {2, 3, 4, 5} and values = {3, 4, 5, 6}. Also create an integer n set to 4 representing the number of packages.

DSA C

# Create arrays weights and values with given values
# Create integer n with value 4

Hint

Use array syntax to create weights and values. Set n to 4.

2

Set the maximum weight limit

Create an integer variable called maxWeight and set it to 5 to represent the truck's weight limit.

DSA C

#include 

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

int main() {
    // Create maxWeight variable
    
    return 0;
}

Hint

Declare int maxWeight = 5; inside main.

3

Implement recursive solution

Write a recursive function called knapsackRecursive that takes three parameters: int i (current index), int w (current weight), and returns the maximum value that can be obtained without exceeding maxWeight. Use the arrays weights and values and the variable n. Then call this function from main with i = 0 and w = 0 and store the result in int resultRec.

DSA C

#include 

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

int knapsackRecursive(int i, int w, int maxWeight) {
    // Your code here
}

int main() {
    int maxWeight = 5;
    // Call knapsackRecursive and store in resultRec
    
    return 0;
}

Hint

Use recursion to try including or excluding the current package. Return the max value.

4

Print the recursive result

Add a printf statement in main to print the text "Recursive result: " followed by the value of resultRec.

DSA C

#include 

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

int knapsackRecursive(int i, int w, int maxWeight) {
    if (i == n) {
        return 0;
    }
    if (w + weights[i] > maxWeight) {
        return knapsackRecursive(i + 1, w, maxWeight);
    } else {
        int include = values[i] + knapsackRecursive(i + 1, w + weights[i], maxWeight);
        int exclude = knapsackRecursive(i + 1, w, maxWeight);
        return include > exclude ? include : exclude;
    }
}

int main() {
    int maxWeight = 5;
    int resultRec = knapsackRecursive(0, 0, maxWeight);
    // Print the recursive result
    
    return 0;
}

Hint

Use printf("Recursive result: %d\n", resultRec); to print.