# Maximum Units

Posted in  Vinay Khatri
Last updated on December 4, 2023

## 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]]`

`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 < a;
});
// variable to store the resultant boxes
int ans = 0;

// iterate the array
for (auto & b: arr) {
int c = min(b, t);
ans += c * b, 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 - a);

// variable to store the resultant boxes
int ans = 0;

// iterate the array
for (int[] b : arr) {
int c = Math.min(b, t);

ans += c * b;
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, reverse=True)

# variable to store the resultant c
ans = 0

# iterate the array
for b,n in arr:
c = min(b, t)

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``