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.
2 Answers 2
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)
).
-
1\$\begingroup\$ Just to clarify: explicit disables copy-list-initialization, such as
Item i = {1, 2, 3};
\$\endgroup\$L. F.– L. F.2020年03月30日 01:53:07 +00:00Commented Mar 30, 2020 at 1:53 -
1\$\begingroup\$ @L.F. Ah, one of those little details in the language I seem to have missed. I updated my answer. \$\endgroup\$1201ProgramAlarm– 1201ProgramAlarm2020年03月30日 03:55:08 +00:00Commented Mar 30, 2020 at 3:55
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
Item item(...whatever);
thenitems.push_back(item);
\$\endgroup\$