Relaxed Bin Packing

relaxedbinpacking.cpp

// 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;
    }
    
}