Maximum Units

Posted in

Maximum Units

Vinay Khatri
Last updated on September 24, 2022

    Problem

    You have to place a number of boxes into the truck. You are given a 2D array where each element represents the number of boxes of type ‘i’ and the number of units in the box of type ‘i’, respectively. You are also given an integer, which is the maximum number of boxes that can be put on the truck. You can choose any boxes to put on the truck as long as the number of boxes does not exceed the truck size. Your task is to find the maximum total number of units that can be put on the truck.

    Sample Input

    [[1, 3], [2, 2], [3,1]]

    Sample Output

    8

    Explanation

    We will take all the boxes of the first and second types and a box of the third type. Total number of units will be = (1 * 3) + (2 * 2) + (1 * 1) = 8.

    Approach

    Simply put, we must prioritize the more valuable boxes first. To accomplish this, we must sort the box types array in decreasing order by the number of units per box. Then we can iterate through B, adding as many boxes as possible at each step until we reach the truck size (T).

    To our answer variable, we should add the number of boxes added multiplied by the units per box, and T should be reduced by the same number of boxes. We should return the answer when the truck is full (T == 0) or when the iteration is complete.

    Complexity Analysis

    The time complexity is O(NlogN)) with space complexity of O(1)

    C++ Programming

    #include<bits/stdc++.h>
    
    using namespace std;
    
    // function to find maximum number of boxes
    int maximumUnits(vector < vector < int >> & arr, int t) {
      
      // sort the array in decreasing order
      sort(arr.begin(), arr.end(), [](auto & a, auto & b) {
        return b[1] < a[1];
      });
      // variable to store the resultant boxes
      int ans = 0;
      
      // iterate the array
      for (auto & b: arr) {
        int c = min(b[0], t);
        // update the answer
        ans += c * b[1], t -= c;
        if (!t) return ans;
      }
      return ans;
    }
    
    int main() {
        // initialize the array
      vector < vector < int >> arr {{1, 3}, {2, 2}, {3,1}};
        int t = 4;
        cout << maximumUnits(arr, t);
    }

    Output

    8

    Java Programming

    import java.io.*;
    import java.util.Arrays;
    
    class Solution {
        
        // function to find maximum number of boxes
        public static int maximumUnits(int[][] arr, int t) {
            
            // sort the array in decreasing order
            Arrays.sort(arr, (a,b) -> b[1] - a[1]);
            
            // variable to store the resultant boxes
            int ans = 0;
            
            // iterate the array
            for (int[] b : arr) {
                int c = Math.min(b[0], t);
                
                // update the answer
                ans += c * b[1];
                t -= c;
                if (t == 0) return ans;
            }
            return ans;
        }
        public static void main (String[] args) {
            
            // initialize the array
            int[][] arr = {{1, 3}, {2, 2}, {3,1}};
            int t = 4;
            System.out.println(maximumUnits(arr, t));
        }
    }
    

    Output

    8

    Python Programming

    # function to find maximum number of c
    def maximumUnits(arr, t):
    
        # sort the array in decreasing order
        arr.sort(key=lambda x: x[1], reverse=True)
    
        # variable to store the resultant c
        ans = 0
    
        # iterate the array
        for b,n in arr:
            c = min(b, t)
            
            # update the answer
            ans += c * n
            t -= c
            if t == 0: return ans
        return ans
    
    # initialize the array
    arr = [[1, 3], [2, 2], [3,1]]
    t = 4
    print(maximumUnits(arr, t))

    Output

    8

    People are also reading:

    Leave a Comment on this Post

    0 Comments