Optimal Selection || OPTSLCT

editorial
1

Editorial-Optimal Selection

Problem: Optimal Selection

You’re working in a packaging company. Your task is to use a minimum number of packages required to deliver the goods. You can use Box Size of 1 (Rs 2), 3 (Rs 4), and 5(Rs 6). Write a program to find the minimum number of boxes required to make sure you’re not spending a lot.

Prerequisite:- none

Hint

Use Greedy Algorithm Approach

Short Explanation

To solve this you need to fit the maximum items possible in the Size 5 box if the items are more than 3 and 1. Once box 5 is completely filled, use the same approach for box 3 and box 1. As you are filling the boxes, keep the track of expenditure as well to figure out the total cost of the packing items.

Detailed Explanation

Our goal is to minimize the cost needed to pack all the items into the boxes. To do so, we need to first check if items are greater than or equal to 5, if yes we need to find the total number of boxes that can be completely filled. To find this we can divide the total number of items by 5 and get the number of boxes that can be completely filled using this. Once we get the required number of boxes we can multiply that with the cost of the box which is Rs 6 in this case and get the total cost so far. Now to pack the remaining items we first need to take the modulus (or remainder) of items when divided by 5. After that, we need to repeat the same steps taking that remainder as the total number of items for box 3 and box 1. Finally, we need to print out the total combined cost of all the boxes and a new line after that to successfully solve this problem.

Time Complexity:

O(1) as this is going to remain constant irrespective of the value of N

Space Complexity:

O(1) - no change of space during runtime

Alternate Solution:

None

Author: Sidharth Sethi - techspiritss
Tester: Ramandeep - ramandeep8421
Editorialist: Sidharth Sethi - techspiritss

Tester’s Solution:

Implementation Language: C++

#include <bits/stdc++.h>

using namespace std;

void solve(){
int n;
cin >> n;
assert(n >= 1 && n <= 10000);

int cost=0;

while(n > 0){
   if(n >= 5){
     int cnt = n/5;
     n %= 5;
     cost += (cnt * 6);
   }
   else if(n >= 3){
     int cnt = n/3;
     n %= 3;
     cost += (cnt * 4);
   }
   else{
     cost += (n * 2);
     n = 0;
   }
}