Skip to main content
added 2 characters in body
Source Link
L. F.
  • 9.7k
  • 2
  • 27
  • 70
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 switchswitch_) {
                                  return item.weightprofit * profit;switch_;
                              };
}
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, {});
}
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.weight * profit;
                              };
}
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);
}
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_;
                              };
}
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, {});
}
added 1857 characters in body
Source Link
L. F.
  • 9.7k
  • 2
  • 27
  • 70

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)

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)

added 51 characters in body
Source Link
L. F.
  • 9.7k
  • 2
  • 27
  • 70

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

std::bitset (defined in header ) seems more convenient for enumerating possibilities — std::bitset{13} yields 1101, for example.

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

Source Link
L. F.
  • 9.7k
  • 2
  • 27
  • 70
Loading