- 0
Notifications Mark All Read
- Login
- Get Prime
TCS Coding Questions 2022 Day 2 Slot 1
Coding Question 2 for 2022 (September slot)
In this article, we will discuss about the TCS Coding Question which is asked in the TCS placement test. This type of Coding Questions will help you to crack your upcoming TCS exam as well as during your inteview process.
TCS Coding Question Day 2 Slot 1 – Question 2
Mr. Rao is relocating from place A to B. The moving truck has a maximum capacity C. There are ‘N’ items in the house where each item has a corresponding value (Vi) and weight(Wi). Mr. Rao has to carry only the most valuable items whose total weight does not exceed the capacity of truck. The task here is to find those items (single or combination of items) whose total value (v) will be the maximum and their corresponding weight(w) will not exceed truck capacity(c). Here,
- N= No. of items
- C= Maximum capacity of the truck, an integer value,
- W[0 to N-1]- An array consisting weight of each item
- V[0 to N-1] – An array consisting value of each item.
Example 1:
Input :
- 4 -> Value of N
- 80 -> Value of C
- [10,45,60,90] -> Elements of array v[], where each element is separated by new line.
- [15,20,30,40] -> Elements of array w[], where each element is separated by new line.
Output: 150
Explanation:
- Value=10 weight=15
- Value=45 weight = 20
- Value = 60 weight=30
- Value=90 weight=40
The subsets that can be formed from the array V[], their corresponding weight W[] and comparison with c=80
Value | Total Value | Weight | Total Weight | Valid (total weight(<C) Invalid (total weight>C) |
---|---|---|---|---|
10+45 | 55 | 15+20 | 35 | Valid |
10+60 | 70 | 15+30 | 45 | Valid |
10+90 | 100 | 15+40 | 55 | Valid |
45+60 | 105 | 20+30 | 50 | Valid |
45+90 | 135 | 20+40 | 60 | Valid |
60+90 | 150 | 20+40 | 70 | Valid |
10+45+60 | 115 | 20+40 | 65 | Valid |
10+60+90 | 160 | 20+40 | 85 | Invalid |
10+45+90 | 145 | 20+40 | 75 | Valid |
From the above table, it is perceived that particularly for the valid items, maximum value=150 and their corresponding weight is 70. So the output should be 150.
The input format for testing
First Input – Accept value for N (positive integer number).
Second input : Accept value for C (Positive integer number),
Third input – Accept N number of positive integer number for array v[0…N-1], where each value is separated by a new line.
Fourth input – Accept N positive integer numbers for array [0….N-1], where each value is separated by a new line.
The output format for testing
The output should be a positive integer number (Check the output in Example 1)
Constraints:
- 0<=N<=10
- 0 <= C<=500
- 1<=V[i]<=500
import java.util.*;
class Solution
{
public static int solve(int c,int w[],int val[],int n)
{
if(n==0 || c==0)
return 0;
if(c<w[n-1])
return solve(c,w,val,n-1);
else
return Math.max(solve(c,w,val,n-1),val[n-1]+solve(c-w[n-1],w,val,n-1));
}
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int c=sc.nextInt();
int v[]=new int[n];
int w[]=new int[n];
for(int i=0;i<n;i++)
v[i]=sc.nextInt();
for(int i=0;i<n;i++)
w[i]=sc.nextInt();
System.out.println(solve(c,w,v,n));
}
}
Login/Signup to comment