``````/**
* @file
* @brief Implementation of [0-1 Knapsack Problem]
* (https://en.wikipedia.org/wiki/Knapsack_problem)
*
* @details
* Given weights and values of n items, put these items in a knapsack of
* capacity `W` to get the maximum total value in the knapsack. In other words,
* given two integer arrays `val[0..n-1]` and `wt[0..n-1]` which represent
* values and weights associated with n items respectively. Also given an
* integer W which represents knapsack capacity, find out the maximum value
* subset of `val[]` such that sum of the weights of this subset is smaller than
* or equal to W. You cannot break an item, either pick the complete item or
* don’t pick it (0-1 property)
*
* ### Algorithm
* The idea is to consider all subsets of items and calculate the total weight
* and value of all subsets. Consider the only subsets whose total weight is
* smaller than `W`. From all such subsets, pick the maximum value subset.
*
* @author [Anmol](https://github.com/Anmol3299)
* @author [Pardeep](https://github.com/Pardeep009)
*/

#include <array>
#include <cassert>
#include <iostream>
#include <vector>

/**
* @namespace dynamic_programming
* @brief Dynamic Programming algorithms
*/
namespace dynamic_programming {
/**
* @namespace Knapsack
* @brief Implementation of 0-1 Knapsack problem
*/
namespace knapsack {
/**
* @brief Picking up all those items whose combined weight is below
* given capacity and calculating value of those picked items.Trying all
* possible combinations will yield the maximum knapsack value.
* @tparam n size of the weight and value array
* @param capacity capacity of the carrying bag
* @param weight array representing weight of items
* @param value array representing value of items
* @return maximum value obtainable with given capacity.
*/
template <size_t n>
int maxKnapsackValue(const int capacity, const std::array<int, n> &weight,
const std::array<int, n> &value) {
std::vector<std::vector<int> > maxValue(n + 1,
std::vector<int>(capacity + 1, 0));
// outer loop will select no of items allowed
// inner loop will select capcity of knapsack bag
int items = sizeof(weight) / sizeof(weight);
for (size_t i = 0; i < items + 1; ++i) {
for (size_t j = 0; j < capacity + 1; ++j) {
if (i == 0 || j == 0) {
// if no of items is zero or capacity is zero, then maxValue
// will be zero
maxValue[i][j] = 0;
} else if (weight[i - 1] <= j) {
// if the ith item's weight(in actual array it will be at i-1)
// is less than or equal to the allowed weight i.e. j then we
// can pick that item for our knapsack. maxValue will be the
// obtained either by picking the current item or by not picking
// current item

// picking current item
int profit1 = value[i - 1] + maxValue[i - 1][j - weight[i - 1]];

// not picking current item
int profit2 = maxValue[i - 1][j];

maxValue[i][j] = std::max(profit1, profit2);
} else {
// as weight of current item is greater than allowed weight, so
// maxProfit will be profit obtained by excluding current item.
maxValue[i][j] = maxValue[i - 1][j];
}
}
}

// returning maximum value
return maxValue[items][capacity];
}
}  // namespace knapsack
}  // namespace dynamic_programming

/**
* @brief Function to test above algorithm
* @returns void
*/
static void test() {
// Test 1
const int n1 = 3;                             // number of items
std::array<int, n1> weight1 = {10, 20, 30};   // weight of each item
std::array<int, n1> value1 = {60, 100, 120};  // value of each item
const int capacity1 = 50;                     // capacity of carrying bag
const int max_value1 = dynamic_programming::knapsack::maxKnapsackValue(
capacity1, weight1, value1);
const int expected_max_value1 = 220;
assert(max_value1 == expected_max_value1);
std::cout << "Maximum Knapsack value with " << n1 << " items is "
<< max_value1 << std::endl;

// Test 2
const int n2 = 4;                               // number of items
std::array<int, n2> weight2 = {24, 10, 10, 7};  // weight of each item
std::array<int, n2> value2 = {24, 18, 18, 10};  // value of each item
const int capacity2 = 25;                       // capacity of carrying bag
const int max_value2 = dynamic_programming::knapsack::maxKnapsackValue(
capacity2, weight2, value2);
const int expected_max_value2 = 36;
assert(max_value2 == expected_max_value2);
std::cout << "Maximum Knapsack value with " << n2 << " items is "
<< max_value2 << std::endl;
}

/**
* @brief Main function
* @returns 0 on exit
*/
int main() {
// Testing
test();
return 0;
}
``````

#### 0 1 Knapsack  