-
-
Notifications
You must be signed in to change notification settings - Fork 7.3k
/
Copy pathunbounded_0_1_knapsack.cpp
173 lines (159 loc) · 6.87 KB
/
unbounded_0_1_knapsack.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
/**
* @file
* @brief Implementation of the Unbounded 0/1 Knapsack Problem
*
* @details
* 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](https://github.com/yeolesanskruti)
* @see dynamic_programming/0_1_knapsack.cpp
*/
#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
* @brief Namespace for dynamic programming algorithms
*/
namespace dynamic_programming {
/**
* @namespace Knapsack
* @brief Implementation of unbounded 0-1 knapsack problem
*/
namespace unbounded_knapsack {
/**
* @brief Recursive function to calculate the maximum value obtainable using
* an unbounded knapsack approach.
*
* @param i Current index in the value and weight vectors.
* @param W Remaining capacity of the knapsack.
* @param val Vector of values corresponding to the items.
* @note "val" data type can be changed according to the size of the input.
* @param wt Vector of weights corresponding to the items.
* @note "wt" data type can be changed according to the size of the input.
* @param dp 2D vector for memoization to avoid redundant calculations.
* @return The maximum value that can be obtained for the given index and
* capacity.
*/
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
}
/**
* @brief Wrapper function to initiate the unbounded knapsack calculation.
*
* @param N Number of items.
* @param W Maximum weight capacity of the knapsack.
* @param val Vector of values corresponding to the items.
* @param wt Vector of weights corresponding to the items.
* @return The maximum value that can be obtained for the given capacity.
*/
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
/**
* @brief self test implementation
* @return void
*/
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;
}
/**
* @brief main function
* @return 0 on successful exit
*/
int main() {
tests(); // Run self test implementation
return 0;
}