This post is completed by 1 user

  • 0
 Add to List
Hard

478. Efficient Robot Problem - Find Minimum Trips

Problem: There is N number of items that need to be transferred from one place to another by a robot. Each item has a specific weight. The robot can carry maximum weight K in one trip. You need to come up with an algorithm to find out the minimum number of trips that the robot has to make to transfer all N items.

Note: All the items weight is less than equal to K.

Example:

Items = [2, 3, 1, 5, 3, 6, 2, 2]
K = 6
Output:
[2, 2, 2]
[3, 3]
[5, 1]
[6]
Minimum Trips for robot: 4

Items = [2, 3, 1, 5, 3, 6, 2, 2]
K = 10
Output:
[6, 1, 2]
[5, 3, 2]
[3, 2]
Minimum Trips for Robot: 3

Approach: Sorting. 

  • Initialize current_weight = 0.
  • Sort all the items in ascending order.
  • Picking elements from right to left and keep adding the weights to current_weight until current_weight<K.
  • Now start picking elements from left to right and adding the weights to current_weight until current_weight<K.
  • Once the previous two steps are over, either current_weight = K or current_weight<K. Send the robot with picked items and add one to trips. 
  • Repeat the above steps until all the items are sent. 
  • Use visited [] to mark if the item is already sent or not.
  • Use a list to track the items sent in each trip.

Output:

[6]
[5, 1]
[3, 3]
[2, 2, 2]
Minimum Trips for Robot: 4

Related Problems: