unbounded_0_1_knapsack.cpp

Go to the documentation of this file.

 
#include <cassert>   // For using assert function to validate test cases
#include <cstdint>   // For fixed-width integer types like std::uint16_t
#include <iostream>  // Standard input-output stream
#include <vector>    // Standard library for using dynamic arrays (vectors)

namespace dynamic_programming {

namespace unbounded_knapsack {

std::uint16_t KnapSackFilling(std::uint16_t i, std::uint16_t W,
                              const std::vector<std::uint16_t>& val,
                              const std::vector<std::uint16_t>& wt,
                              std::vector<std::vector<int>>& dp) {
    if (i == 0) {
        if (wt[0] <= W) {
            return (W / wt[0]) *
                   val[0];  // Take as many of the first item as possible
        } else {
            return 0;  // Can't take the first item
        }
    }
    if (dp[i][W] != -1)
        return dp[i][W];  // Return result if available
 
    int nottake =
        KnapSackFilling(i - 1, W, val, wt, dp);  // Value without taking item i
    int take = 0;
    if (W >= wt[i]) {
        take = val[i] + KnapSackFilling(i, W - wt[i], val, wt,
                                        dp);  // Value taking item i
    }
    return dp[i][W] =
               std::max(take, nottake);  // Store and return the maximum value
}

std::uint16_t unboundedKnapsack(std::uint16_t N, std::uint16_t W,
                                const std::vector<std::uint16_t>& val,
                                const std::vector<std::uint16_t>& wt) {
    if (N == 0)
        return 0;  // Expect 0 since no items
    std::vector<std::vector<int>> dp(
        N, std::vector<int>(W + 1, -1));  // Initialize memoization table
    return KnapSackFilling(N - 1, W, val, wt, dp);  // Start the calculation
}
 
}  // namespace unbounded_knapsack
 
}  // namespace dynamic_programming

static void tests() {
    // Test Case 1
    std::uint16_t N1 = 4;                            // Number of items
    std::vector<std::uint16_t> wt1 = {1, 3, 4, 5};   // Weights of the items
    std::vector<std::uint16_t> val1 = {6, 1, 7, 7};  // Values of the items
    std::uint16_t W1 = 8;  // Maximum capacity of the knapsack
    // Test the function and assert the expected output
    assert(dynamic_programming::unbounded_knapsack::unboundedKnapsack(
               N1, W1, val1, wt1) == 48);
    std::cout << "Maximum Knapsack value "
              << dynamic_programming::unbounded_knapsack::unboundedKnapsack(
                     N1, W1, val1, wt1)
              << std::endl;
 
    // Test Case 2
    std::uint16_t N2 = 3;                              // Number of items
    std::vector<std::uint16_t> wt2 = {10, 20, 30};     // Weights of the items
    std::vector<std::uint16_t> val2 = {60, 100, 120};  // Values of the items
    std::uint16_t W2 = 5;  // Maximum capacity of the knapsack
    // Test the function and assert the expected output
    assert(dynamic_programming::unbounded_knapsack::unboundedKnapsack(
               N2, W2, val2, wt2) == 0);
    std::cout << "Maximum Knapsack value "
              << dynamic_programming::unbounded_knapsack::unboundedKnapsack(
                     N2, W2, val2, wt2)
              << std::endl;
 
    // Test Case 3
    std::uint16_t N3 = 3;                           // Number of items
    std::vector<std::uint16_t> wt3 = {2, 4, 6};     // Weights of the items
    std::vector<std::uint16_t> val3 = {5, 11, 13};  // Values of the items
    std::uint16_t W3 = 27;  // Maximum capacity of the knapsack
    // Test the function and assert the expected output
    assert(dynamic_programming::unbounded_knapsack::unboundedKnapsack(
               N3, W3, val3, wt3) == 27);
    std::cout << "Maximum Knapsack value "
              << dynamic_programming::unbounded_knapsack::unboundedKnapsack(
                     N3, W3, val3, wt3)
              << std::endl;
 
    // Test Case 4
    std::uint16_t N4 = 0;                  // Number of items
    std::vector<std::uint16_t> wt4 = {};   // Weights of the items
    std::vector<std::uint16_t> val4 = {};  // Values of the items
    std::uint16_t W4 = 10;                 // Maximum capacity of the knapsack
    assert(dynamic_programming::unbounded_knapsack::unboundedKnapsack(
               N4, W4, val4, wt4) == 0);
    std::cout << "Maximum Knapsack value for empty arrays: "
              << dynamic_programming::unbounded_knapsack::unboundedKnapsack(
                     N4, W4, val4, wt4)
              << std::endl;
 
    std::cout << "All test cases passed!" << std::endl;
}

int main() {
    tests();  // Run self test implementation
    return 0;
}