0
\$\begingroup\$

You are assigned to put some amount of boxes onto one truck. You are given a 2D vector of box_types where box_type[0] is the number of a type of box and box_type[1] is the units per box for that type. You are also given an integer value for the truck size, this the maximum boxes you can put in the truck. Return the maximum unit that can be put in a given truck.

Example

input : box_types = {{1, 3}, {2, 2}, {3, 1}} truck_size = 4

output: 8

Explanation:

There are

  • 1 box of type 0
  • 2 box of type 1
  • 3 box of type 2

where 0, 1, 2 is the index of the vector

You can take all the boxes of the first type, second type and one box from the third type

max_unit = (1 * 3) + (2 * 2) + (1 * 1) = 8

Here is my implementation

#include <iostream>
#include <algorithm>
#include <vector>

void sort_boxtypes(std::vector<std::vector<int>> &box_types)
{
    std::sort(
        box_types.begin(), box_types.end(), 
        [](const std::vector<int>& a, const std::vector<int> &b)
        {return a[1] > b[1]; }
    );
}
int maximum_units(std::vector<std::vector<int>> box_types, int truck_size)
{
    sort_boxtypes(box_types);
    int max_unit = 0;
    for(const auto& box_type : box_types)
    {
        truck_size -= box_type[0];
        if(truck_size >= 0)
            max_unit += box_type[0] * box_type[1];
        else
        {
            max_unit += (box_type[0] + truck_size) * box_type[1];
            return max_unit;
        } 
    }
    return max_unit;
}

int main()
{
    std::vector<std::vector<int>> box_types = {{5, 10}, {2, 5}, {4, 7}, {3, 9}};
    int max = maximum_units(box_types, 10);
    std::cout << max << '\n';
    
}


\$\endgroup\$

1 Answer 1

1
\$\begingroup\$
  • Names are better then indices. Consider

      struct box_type {
          int amount;
          int capacity;
      };
    

    box.amount seems cleaner that box[0].

  • Along the same line, declaring such a structure would let you define

      friend bool box_type::operator <(const box_type& l, const box_type& r) {
          return l.capacity < r.capacity;
      }
    

    and eliminate a lambda, as well as sort_boxtypes function.

  • I don't like max_units (it sounds like there are min_units somewhere). Similarly, truck_size is a truck size, a constant; consider a remaining_size or something like that.

  • It feels that a truck_size >= 0 comparison shall be done beforehand. Consider

      std::sort(boxes.begin(), boxes.end());
      for (auto box = boxes.rbegin(); box != boxes.rend(); ++box) {
          auto the_load = std::min(box.amount, remaining_size());
          units += box.capacity * box.amount;
          remaining_size -= the_load;
          if (remaining_size == 0) {
              break;
          }
      }
      return units;
    
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.