Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Relaxed Bin Packing
// I was bored so I programmed the binpacking relaxed problem
#include <iostream>
#include <array>
#include <algorithm>
#include <functional>
struct Item {
unsigned int number;
unsigned int utility;
double weight;
[[nodiscard]] double util() const {
return static_cast<double>(utility) / weight;
}
};
int main()
{
std::array<Item, 6> items{{
{0, 12, 0.2},
{1, 7, 2.},
{2, 4, 0.8},
{3, 6, 1},
{4, 8, 1},
{5, 30, 3}
}};
std::sort(items.begin(), items.end(),
[](const Item & lhs, const Item & rhs) {
return std::greater<double>()(lhs.util(), rhs.util());
});
double left_capacity = 4;
size_t i = 0;
while (i != items.size() && left_capacity > 0) {
if (items[i].weight <= left_capacity) {
left_capacity -= items[i].weight;
printf("Picked 1 item %d\n", items[i].number);
} else {
double parts = static_cast<double>(left_capacity) / items[i].weight;
printf("Picked %lf item %d\n", parts, items[i].number);
left_capacity = 0;
}
++i;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment