Petrol Pump
Few words from CodingHumans : Don't Just copy paste the solution, try to analyze the problem and solve it without looking by taking the the solution as a hint or a reference . Your understanding of the solution matters.
Solution 1:
( c )
#include <stdio.h>
int main(void) {
int n=0, x, i, j, s = 0;
int a[51];
while((scanf("%d",&x))!=-1)
{
a[n++]=x;
s += x;
}
int d[n+1][s+1];
for(i=0 ; i<=n ; ++i)
d[i][0] = 1;
for(i=1 ; i<=s ; ++i)
d[0][i] = 0;
for(i=1 ; i<=n ; ++i)
for(j=1 ; j<=s ; ++j)
{
d[i][j] = d[i-1][j];
if(a[i-1] <= j)
d[i][j] = d[i][j] | d[i-1][j - a[i-1]];
}
int an = s;
for(i=s/2 ; i>=0 ; --i)
if(d[n][i])
{
an = s - i;
break;
}
printf("%d",an);
return 0;
}
solution 2:
( c++ )
#include<bits/stdc++.h>
using namespace std;
int subset(vector<int> &arr, int s) {
int n = arr.size();
bool dp[n+1][s+1];
for(int i=0; i<=s; i++) dp[0][i] = false;
for(int i=0; i<=n; i++) dp[i][0] = true;
for(int i=1; i<=n; i++) {
for(int j=1; j<=s; j++) {
dp[i][j] = dp[i-1][j];
if(arr[i-1] <= j) dp[i][j] = dp[i][j] || dp[i-1][j-arr[i-1]];
}
}
int i=s;
for(; i>=0; i--) {
if(dp[n][i]) break;
}
return i;
}
int main() {
vector<int> arr;
int sum=0;
string inp, t;
getline(cin, inp);
stringstream ss(inp);
while(ss >> t) {
int n = stoi(t);
arr.push_back(n);
sum += n;
}
int ans = subset(arr, sum/2);
cout << max(ans, sum-ans);
return 0;
}
Problem Created By TCS MockVita 2 2020
If you have any doubts regarding this problem or need the solution in other programming languages then leave a comment down below .
Problem Description
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.
Constraints
1<= Number of vehicles < 50.
0 <= Quantity of petrol required in any vehicle <= 200
Input Format
First line will provide the quantity of petrol (separated by space) that can be filled in each vehicle.
Output
Shortest possible time to fill petrol in all the vehicles.
Timeout
1
Explanation
Example 1
Input
1 2 3 4 5 10 11 3 6 16
Output
31
Explanation
First Petrol vending machine will cater to vehicles taking - 16, 6, 4, 3, 2 litres of petrol (Total 31 sec)
Second machine will cater to vehicles taking - 11, 10, 5, 3, 1 litres of petrol (Total 30 sec)
Example 2
Input
25 30 35 20 90 110 45 70 80 12 30 35 85
Output
335
Explanation
First Petrol vending machine will cater to vehicles taking - 80, 45, 35, 30, 25, 12, 85, 20 litres of petrol.
Second machine will cater to vehicles taking - 90, 70, 35, 30, 110 litres of petrol. Since second machine will take more time, total time to fill petrol in all vehicles will be 335 seconds.
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.
Constraints
1<= Number of vehicles < 50.
0 <= Quantity of petrol required in any vehicle <= 200
Input Format
First line will provide the quantity of petrol (separated by space) that can be filled in each vehicle.
Output
Shortest possible time to fill petrol in all the vehicles.
Timeout
1
Explanation
Example 1
Input
1 2 3 4 5 10 11 3 6 16
Output
31
Explanation
First Petrol vending machine will cater to vehicles taking - 16, 6, 4, 3, 2 litres of petrol (Total 31 sec)
Second machine will cater to vehicles taking - 11, 10, 5, 3, 1 litres of petrol (Total 30 sec)
Example 2
Input
25 30 35 20 90 110 45 70 80 12 30 35 85
Output
335
Explanation
First Petrol vending machine will cater to vehicles taking - 80, 45, 35, 30, 25, 12, 85, 20 litres of petrol.
Second machine will cater to vehicles taking - 90, 70, 35, 30, 110 litres of petrol. Since second machine will take more time, total time to fill petrol in all vehicles will be 335 seconds.
Recommended: Please try your approach on your integrated development environment (IDE) first, before moving on to the solution.
Few words from CodingHumans : Don't Just copy paste the solution, try to analyze the problem and solve it without looking by taking the the solution as a hint or a reference . Your understanding of the solution matters.
HAPPY CODING 😁
( c )
#include <stdio.h>
int main(void) {
int n=0, x, i, j, s = 0;
int a[51];
while((scanf("%d",&x))!=-1)
{
a[n++]=x;
s += x;
}
int d[n+1][s+1];
for(i=0 ; i<=n ; ++i)
d[i][0] = 1;
for(i=1 ; i<=s ; ++i)
d[0][i] = 0;
for(i=1 ; i<=n ; ++i)
for(j=1 ; j<=s ; ++j)
{
d[i][j] = d[i-1][j];
if(a[i-1] <= j)
d[i][j] = d[i][j] | d[i-1][j - a[i-1]];
}
int an = s;
for(i=s/2 ; i>=0 ; --i)
if(d[n][i])
{
an = s - i;
break;
}
printf("%d",an);
return 0;
}
solution 2:
( c++ )
#include<bits/stdc++.h>
using namespace std;
int subset(vector<int> &arr, int s) {
int n = arr.size();
bool dp[n+1][s+1];
for(int i=0; i<=s; i++) dp[0][i] = false;
for(int i=0; i<=n; i++) dp[i][0] = true;
for(int i=1; i<=n; i++) {
for(int j=1; j<=s; j++) {
dp[i][j] = dp[i-1][j];
if(arr[i-1] <= j) dp[i][j] = dp[i][j] || dp[i-1][j-arr[i-1]];
}
}
int i=s;
for(; i>=0; i--) {
if(dp[n][i]) break;
}
return i;
}
int main() {
vector<int> arr;
int sum=0;
string inp, t;
getline(cin, inp);
stringstream ss(inp);
while(ss >> t) {
int n = stoi(t);
arr.push_back(n);
sum += n;
}
int ans = subset(arr, sum/2);
cout << max(ans, sum-ans);
return 0;
}
Problem Created By TCS MockVita 2 2020
If you have any doubts regarding this problem or need the solution in other programming languages then leave a comment down below .
This comment has been removed by the author.
ReplyDeletecode will be python
ReplyDeletecan u please write python code please
ReplyDeleteSure buddy, This is the solution we applied on python
Deleteimport sys
def findMin(a, n):
su = 0
su = sum(a)
dp = [[0 for i in range(su + 1)]
for j in range(n + 1)]
for i in range(n + 1):
dp[i][0] = True
for j in range(1, su + 1):
dp[0][j] = False
for i in range(1, n + 1):
for j in range(1, su + 1):
dp[i][j] = dp[i - 1][j]
if a[i - 1] <= j:
dp[i][j] |= dp[i - 1][j - a[i - 1]]
diff = sys.maxsize
for j in range(su // 2, -1, -1):
if dp[n][j] == True:
diff = su - (2 * j)
ans1 = (j)+diff
break
return ans1
a=list(map(int,input().split()))
n = len(a)
print(findMin(a, n),end="")