Algoritmo que encuentra las mejores cajas para agregarlas a la bolsa del Grinch #regalaconocimiento

platzi.cpp

#include <iostream>
#include <string>
#include <vector>

const unsigned maxBagWeight = 150;

struct Box {
    std::string name;
    unsigned money;
    unsigned weight;
    double moneyPerWeight;

    Box(std::string name, int money, int weight) : name(name), money(money), weight(weight), moneyPerWeight(double(money)/weight){}
};

void printBag(std::vector<Box> bag) {
    unsigned bagWeight = 0, bagMoney = 0;
    std::cout << "Cajas que el grinch debe llevar:" << std::endl << std::endl;

    for (Box box : bag) {
        bagWeight += box.weight;
        bagMoney += box.money;
        std::cout << box.name << ": " << "$" << box.money << " usd, " << box.weight << " Kg" << std::endl;
    }

    std::cout << std::endl << "Peso total: " << bagWeight << " Kg" << std::endl << "Dinero total: $" << bagMoney << " usd" << std::endl;
    std::cout << "¡Feliz no navidad!" << std::endl;
}

int main() {
    // Datos de entrada
    std::vector<Box> boxes = {Box("Caja A", 100, 40), Box("Caja B",20, 10), Box("Caja C", 40, 120), Box("Caja D" ,20, 20), Box("Caja E",10, 10)};
    
    // Bolsa del grinch
    std::vector<Box> bag;
    unsigned bagWeight = 0;
    
    // Variables auxiliares
    unsigned bestBoxIndex;
    unsigned totalWeight;

    // Ciclo que agrega las cajas con mejor beneficio a la bolsa (mas dinero por menor peso) hasta que se llene
    while (true) {
        bestBoxIndex = 0;
        
        for (unsigned i = 1; i < boxes.size(); i++) {
            if (boxes[i].moneyPerWeight > boxes[bestBoxIndex].moneyPerWeight) bestBoxIndex = i;
        }

        totalWeight = bagWeight + boxes[bestBoxIndex].weight;

        if (totalWeight <= maxBagWeight) {
            bag.push_back(boxes[bestBoxIndex]);
            bagWeight = totalWeight;
            boxes.erase(boxes.begin() + bestBoxIndex);
        } else break;
    }

    printBag(bag);
}