0/1 knapsack algorithm implementation with possibilities vector

Question

The following code uses dynamic approach to solve 0/1 knapsack problem. (I know the maximum profit function I have used is not as good as the one I have defined here and I still am working on that 😅. Are any optimizations possible for the following code?

#include "algorithms.h"

struct Item {
    int index = 1;
    int profit = 1;
    int weight = 1;
    Item() = delete;
    explicit Item(int i, int _profit, int w) {
        index = i;
        profit = _profit;
        weight = w;
    }
    bool operator<(const Item& item) {
        return this->profit < item.profit;
    }
    bool operator<=(const Item& item) {
        return this->profit <= item.profit;
    }
    bool operator>(const Item& item) {
        return this->profit > item.profit;
    }
    bool operator>=(const Item& item) {
        return this->profit >= item.profit;
    }
    friend std::ostream& operator<<(std::ostream& out, const Item item) {
        out << item.index;
        return out;
    }
};

long weight(const std::vector<Item>& item_list, const std::vector<int>& item_switch) {
    long sum = 0;
    for (int i = 0; i < item_switch.size(); i++) {
        sum += item_switch[i] * item_list[i].weight;
    }
    return sum;
}

long profit(const std::vector<Item>& item_list, const std::vector<int>& item_switch) {
    long sum = 0;
    for (int i = 0; i < item_switch.size(); i++) {
        sum += item_switch[i] * item_list[i].profit;
    }
    return sum;
}

void increment(std::vector<int>& vec) {
    auto it_bit = vec.end();
    it_bit--;
    while (*it_bit == 1) {
        *it_bit = 0;
        if (it_bit == vec.begin()) {
            return;
        }
        it_bit--;
    }
    *it_bit = 1;
}

int main() {
    long M = 25;
    Item i1(1, 10, 9);
    Item i2(2, 12, 8);
    Item i3(3, 14, 12);
    Item i4(4, 16, 14);
    std::vector<Item> items = { i1,i2,i3,i4 };
    std::vector<int> enable(4,0);
    std::vector<std::vector<int>> possible;
    for (int i = 1; i <= 16; i++) {
        if (weight(items, enable) <= M) {
            possible.push_back(enable);
        }
        increment(enable);
    }
    long pr = 0;
    for (int i = 0; i < possible.size(); i++) {
        long temp = profit(items, possible[i]);
        if (temp > pr) {
            pr = temp;
        }
    }
    std::cout << pr;
    return 0;
}

P.S. I did not implement the nice suggestion here regarding creation of objects, as during the assignment submission, I am supposed to make objects at run-time.

Answer 1

Since you declare a three parameter constructor, the default constructor will not be implicitly defined, so it does not need to be explicitly deleted. There's no real harm in providing a default constructor, since you have initializers for all your members. Alternatively, since the only constructor you supply requires three parameters that initialize all three members of your class, you do not need to provide initializers for them (although doing so can lead to fewer problems in the future if this is expanded on).

The comparison operators should a be declared as const functions. The use of this-> in them is not necessary.

The output operator should take item as a reference to avoid making a copy.

The weight and profit functions assume that both provided vectors have the same size. The size used to end the loop can be stored in a variable to avoid potentially recomputing it every time.

In increment, predecrement should be used for iterators (--it_bit;) to avoid making an unnecessary copy. Have you considered using reverse iterators here (using vec.rbegin())?

The last for loop in main can use the range-for-loop (e.g. for (auto p: possible)).

Answer 2

Loops

for (int i = 0; i < item_switch.size(); i++) {

Your loops have a common problem: the correct type for traversing a std::vector<T> via index is std::vector<T>::size_type (std::size_t is fine too). However, a better solution is to eliminate loops altogether using std::inner_product (defined in header <numeric>) and std::plus (defined in header <functional>):

long weight(const std::vector<Item>& item_list, const std::vector<int>& item_switch)
{
    return std::inner_product(item_list.begin(), item_list.end(),
                              item_switch.begin(), item_switch.end(),
                              0L, std::plus{}, [](const Item& item, int switch_) {
                                  return item.weight * switch_;
                              };
}

long profit(const std::vector<Item>& item_list, const std::vector<int>& item_switch)
{
    return std::inner_product(item_list.begin(), item_list.end(),
                              item_switch.begin(), item_switch.end(),
                              0L, std::plus{}, [](const Item& item, int switch_) {
                                  return item.profit * switch_;
                              };
}

Or, with range-v3:

long weight(const std::vector<Item>& item_list, const std::vector<int>& item_switch)
{
    return ranges::inner_product(item_list, item_switch, 0L, {}, {}, &Item::weight, {});
}

long profit(const std::vector<Item>& item_list, const std::vector<int>& item_switch)
{
    return ranges::inner_product(item_list, item_switch, 0L, {}, {}, &Item::profit, {});
}

Enumerating possibilities

std::bitset (defined in header ) seems more convenient for enumerating possibilities if the number of elements is fixed at compile-time — std::bitset<4>{13} yields 1101, for example.

This loop:

for (int i = 0; i < possible.size(); i++) {
    long temp = profit(items, possible[i]);
    if (temp > pr) {
        pr = temp;
    }
}

should be replaced by std::max_element.

My version

Just for fun, I rewrote the program in a functional style using C++20 and range-v3:

#include <array>
#include <cstddef>
#include <iostream>
#include <range/v3/all.hpp>

// for convenience
constexpr auto operator""_zu(unsigned long long num) noexcept
{
    return static_cast<std::size_t>(num);
}

namespace views = ranges::views;

using profit_type = long long;
using weight_type = long long;

struct Item {
    int weight;
    int profit;
};

template <std::size_t N>
profit_type knapsack(const std::array<Item, N>& items, weight_type max_weight)
{
    return ranges::max(
          views::iota(0ULL, 1ULL << items.size())
        | views::transform([](auto code) { return std::bitset<N>{code}; })
        | views::filter([&](const auto& mask) {
              auto weight = ranges::accumulate(
                  views::iota(0_zu, N) | views::filter([&](auto i) { return mask[i]; }),
                  weight_type{0}, {}, [&](auto i) { return items[i].weight; }
              );
              return weight <= max_weight;
          })
        | views::transform([&](const auto& mask) {
              return ranges::accumulate(
                  views::iota(0_zu, N) | views::filter([&](auto i) { return mask[i]; }),
                  profit_type{0}, {}, [&](auto i) { return items[i].profit; }
              );
          })
    );
}

Example usage:

int main()
{
    std::cout << knapsack(
        std::to_array<Item>({{10, 60}, {20, 100}, {30, 120}}), 50
    );
}

Output:

220

(live demo)