0_1_knapsack.cpp

Go to the documentation of this file.

 
#include <array>
#include <cassert>
#include <iostream>
#include <vector>
 
namespace dynamic_programming {
namespace knapsack {
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 the capacity of the knapsack bag
    int items = sizeof(weight) / sizeof(weight[0]);
    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 the 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 the current item
                int profit1 = value[i - 1] + maxValue[i - 1][j - weight[i - 1]];
 
                // not picking the current item
                int profit2 = maxValue[i - 1][j];
 
                maxValue[i][j] = std::max(profit1, profit2);
            } else {
                // as the weight of the current item is greater than the allowed weight, so
                // maxProfit will be profit obtained by excluding the current item.
                maxValue[i][j] = maxValue[i - 1][j];
            }
        }
    }
 
    // returning maximum value
    return maxValue[items][capacity];
}
}  // namespace knapsack
}  // namespace dynamic_programming
 
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;
}
 
int main() {
    // Testing
    test();
    return 0;
}