unbounded_0_1_knapsack.cpp File Reference

Implementation of the Unbounded 0/1 Knapsack Problem. More...

#include <cassert>
#include <cstdint>
#include <iostream>
#include <vector>

Include dependency graph for unbounded_0_1_knapsack.cpp:

Go to the source code of this file.

Namespaces
namespace	dynamic_programming
	Dynamic Programming algorithms.
namespace	Knapsack
	Implementation of 0-1 Knapsack problem.

Functions
std::uint16_t	dynamic_programming::unbounded_knapsack::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)
	Recursive function to calculate the maximum value obtainable using an unbounded knapsack approach.
std::uint16_t	dynamic_programming::unbounded_knapsack::unboundedKnapsack (std::uint16_t N, std::uint16_t W, const std::vector< std::uint16_t > &val, const std::vector< std::uint16_t > &wt)
	Wrapper function to initiate the unbounded knapsack calculation.
static void	tests ()
	self test implementation
int	main ()
	main function

Detailed Description

Implementation of the Unbounded 0/1 Knapsack Problem.

The Unbounded 0/1 Knapsack problem allows taking unlimited quantities of each item. The goal is to maximize the total value without exceeding the given knapsack capacity. Unlike the 0/1 knapsack, where each item can be taken only once, in this variation, any item can be picked any number of times as long as the total weight stays within the knapsack's capacity.

Given a set of N items, each with a weight and a value, represented by the arrays wt and val respectively, and a knapsack with a weight limit W, the task is to fill the knapsack to maximize the total value.

Note

weight and value of items is greater than zero

Algorithm

The approach uses dynamic programming to build a solution iteratively. A 2D array is used for memoization to store intermediate results, allowing the function to avoid redundant calculations.

Author

Sanskruti Yeole

See also

dynamic_programming/0_1_knapsack.cpp

Definition in file unbounded_0_1_knapsack.cpp.

Function Documentation

KnapSackFilling()

std::uint16_t dynamic_programming::unbounded_knapsack::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 )

Recursive function to calculate the maximum value obtainable using an unbounded knapsack approach.

Parameters

i	Current index in the value and weight vectors.
W	Remaining capacity of the knapsack.
val	Vector of values corresponding to the items.

Note

"val" data type can be changed according to the size of the input.

Parameters

wt	Vector of weights corresponding to the items.

Note

"wt" data type can be changed according to the size of the input.

Parameters

dp	2D vector for memoization to avoid redundant calculations.

Returns

The maximum value that can be obtained for the given index and capacity.

Definition at line 58 of file unbounded_0_1_knapsack.cpp.

                                                             {
    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
}

main()

int main

(

void

)

main function

Returns

0 on successful exit

Definition at line 170 of file unbounded_0_1_knapsack.cpp.

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

tests()

static void tests ( )

static

self test implementation

Returns

void

Definition at line 111 of file unbounded_0_1_knapsack.cpp.

                    {
    // 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;
}

unboundedKnapsack()

std::uint16_t dynamic_programming::unbounded_knapsack::unboundedKnapsack	(	std::uint16_t	N,
		std::uint16_t	W,
		const std::vector< std::uint16_t > &	val,
		const std::vector< std::uint16_t > &	wt )

Wrapper function to initiate the unbounded knapsack calculation.

Parameters

N	Number of items.
W	Maximum weight capacity of the knapsack.
val	Vector of values corresponding to the items.
wt	Vector of weights corresponding to the items.

Returns

The maximum value that can be obtained for the given capacity.

Definition at line 93 of file unbounded_0_1_knapsack.cpp.

                                                                  {
    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
}