Array ( [0] => [1] => questions [2] => Codevita-Previous-Questions [3] => Petrol-Pump )
A big group of students, starting a long journey on different set of vehicles need to fill petrol in their vehicles.
As group leader you are required to minimize the time they spend at the petrol pump to start the journey at the earliest. You will be given the quantity of petrol (in litres) that can be filled in each vehicle. There are two petrol vending machines at the petrol pump. You need to arrange the vehicles in such a way that they take shortest possible time to fill all the vehicles and provide the time taken in seconds as output. Machine vends petrol @ 1litre/second.
Assume that there is no time lost between switching vehicles to start filling petrol.
First line will provide the quantity of petrol (separated by space) that can be filled in each vehicle.
Shortest possible time to fill petrol in all the vehicles.
1 2 3 4 5 10 11 3 6 16
31
25 30 35 20 90 110 45 70 80 12 30 35 85
335
10 3 5 7
13
Login to see Discussion
This should be solved using Dynamic Programming.
Step-i)create a method min_time which takes arr and n as argument
Step-ii)get the sum of the array elements
Step-iii)create a 2 d array of size sum+1 and n+1
Step-iv)for i in range of value 0 to n+1 assing true to dp[i][0]
Step-v)for i in range of value 1 to sum+1 assign false to dp[0][i]
Step-vi)assign sum+1/2 to half
Step-vii)now for i in range of value 1 to n+1 follow below step
Step-viii)for j in range of value 1 to sum+1 follow below step
Step-ix)update dp[i][j] to dp[i-1][j] and if arr[i-1] <= j then perform dp[i][j] = dp[i][j] or dp[i-1][j-arr[i-1]]
Step-x)for j in range of half to sum-1 if dp[n][j] is true return j else return sum
Step-xi)now take necessary inputs and print the output
Note :
Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.
Login to see Solution