Unbounded Knapsack Problem in DSA C - Build from Scratch

Unbounded Knapsack Problem

📖 Scenario: You are helping a shop owner who wants to fill a knapsack with items to maximize profit. The shop owner can take unlimited quantities of each item.

🎯 Goal: Build a program that calculates the maximum profit possible with a given knapsack capacity and unlimited items.

📋 What You'll Learn

Create arrays for item weights and profits with given values

Create an integer variable for knapsack capacity

Implement the unbounded knapsack logic using dynamic programming

Print the maximum profit achievable

💡 Why This Matters

🌍 Real World

This problem models situations where you can use unlimited quantities of resources to maximize profit, like packing goods or cutting raw materials.

💼 Career

Understanding dynamic programming and knapsack problems is important for software engineers working on optimization, resource allocation, and algorithm design.

1

Create item weights and profits arrays

Create two integer arrays called weights and profits with these exact values: weights = {1, 3, 4, 5} and profits = {10, 40, 50, 70}.

DSA C

# Your code here

Hint

Use array syntax to create weights and profits with the exact values.

2

Add knapsack capacity variable

Add an integer variable called capacity and set it to 8.

DSA C

#include 

int main() {
    int weights[] = {1, 3, 4, 5};
    int profits[] = {10, 40, 50, 70};
    // Your code here
    return 0;
}

Hint

Declare an integer variable capacity and assign it the value 8.

3

Implement unbounded knapsack logic

Implement the unbounded knapsack logic using a for loop with variable w from 1 to capacity, and inside it another for loop with variable i from 0 to 3. Use an integer array dp of size capacity + 1 initialized to zero. Update dp[w] to the maximum profit possible by including items multiple times.

DSA C

#include 

int main() {
    int weights[] = {1, 3, 4, 5};
    int profits[] = {10, 40, 50, 70};
    int capacity = 8;
    int dp[capacity + 1];
    // Your code here
    return 0;
}

Hint

Use dynamic programming array dp to store max profit for each weight. Update dp[w] inside nested loops.

4

Print the maximum profit

Print the maximum profit stored in dp[capacity] using printf.

DSA C

#include 

int main() {
    int weights[] = {1, 3, 4, 5};
    int profits[] = {10, 40, 50, 70};
    int capacity = 8;
    int dp[capacity + 1];

    for (int w = 0; w  dp[w]) {
                    dp[w] = val;
                }
            }
        }
    }

    // Print the maximum profit
    // Your code here
    return 0;
}

Hint

Use printf("%d\n", dp[capacity]); to print the result.