Greedy vs DP How to Know Which to Apply in DSA C - Build Both Approaches

Greedy vs DP: How to Know Which to Apply

📖 Scenario: Imagine you are managing a small delivery service. You have a list of packages, each with a weight and a value. You want to maximize the total value of packages you can carry without exceeding your truck's weight limit.This is a classic problem where you can try two approaches: a simple greedy method or a more careful dynamic programming method.

🎯 Goal: Build a program that first tries a greedy approach to select packages by value-to-weight ratio, then uses dynamic programming to find the best combination. Learn how to decide which method works better.

📋 What You'll Learn

Create an array of packages with exact weights and values

Create a variable for the truck's weight limit

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

Implement a dynamic programming solution for the knapsack problem

Print the total value selected by both methods

💡 Why This Matters

🌍 Real World

Delivery services, resource allocation, and budgeting problems often require choosing the best combination of items under constraints.

💼 Career

Understanding greedy and dynamic programming helps in software engineering roles involving optimization, algorithm design, and problem solving.

1

Create the packages array

Create an array called packages of 4 elements where each element is a struct with weight and value. Use these exact values: package 0: weight 2, value 3; package 1: weight 3, value 4; package 2: weight 4, value 5; package 3: weight 5, value 8.

DSA C

#include 

struct Package {
    int weight;
    int value;
};

int main() {
    // Create the packages array with 4 elements
    // Your code here

Hint

Define packages as an array of 4 Package structs with the given weights and values.

2

Set the truck's weight limit

Create an integer variable called weight_limit and set it to 8.

DSA C

#include 

struct Package {
    int weight;
    int value;
};

int main() {
    struct Package packages[4] = {
        {2, 3},
        {3, 4},
        {4, 5},
        {5, 8}
    };
    // Set the weight limit to 8
    // Your code here

Hint

Just create an integer weight_limit and assign it the value 8.

3

Implement the greedy selection

Write code to select packages greedily by value-to-weight ratio. Create an array selected of 4 integers initialized to 0. Then, select packages in order of highest value/weight ratio without exceeding weight_limit. Use variables total_weight and total_value_greedy to track weight and value. Use a simple sorting approach by swapping packages based on ratio.

DSA C

#include 

struct Package {
    int weight;
    int value;
};

int main() {
    struct Package packages[4] = {
        {2, 3},
        {3, 4},
        {4, 5},
        {5, 8}
    };
    int weight_limit = 8;
    // Implement greedy selection by value-to-weight ratio
    // Your code here

Hint

Sort packages by value/weight ratio, then pick packages while total weight is within limit.

4

Implement dynamic programming and print results

Implement a dynamic programming solution to find the maximum value for the weight limit. Create a 2D array dp of size 5 by 9 (for 4 packages + 1 and weight limit + 1). Fill dp using the knapsack logic. Then print the total value from greedy as Greedy total value: X and from DP as DP total value: Y where X and Y are the computed values.

DSA C

#include 

struct Package {
    int weight;
    int value;
};

int main() {
    struct Package packages[4] = {
        {2, 3},
        {3, 4},
        {4, 5},
        {5, 8}
    };
    int weight_limit = 8;

    int selected[4] = {0, 0, 0, 0};
    int total_weight = 0;
    int total_value_greedy = 0;

    // Simple bubble sort by value/weight ratio descending
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3 - i; j++) {
            double ratio_j = (double)packages[j].value / packages[j].weight;
            double ratio_j1 = (double)packages[j+1].value / packages[j+1].weight;
            if (ratio_j < ratio_j1) {
                struct Package temp = packages[j];
                packages[j] = packages[j+1];
                packages[j+1] = temp;
            }
        }
    }

    for (int i = 0; i < 4; i++) {
        if (total_weight + packages[i].weight <= weight_limit) {
            selected[i] = 1;
            total_weight += packages[i].weight;
            total_value_greedy += packages[i].value;
        }
    }

    // Implement DP knapsack and print results
    // Your code here

Hint

Use the classic knapsack DP approach. Then print both totals exactly as shown.