# TCS Coding Questions 2022 Day 2 Slot 1

## Coding Question 2 for 2022 (September slot) ### 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

ValueTotal ValueWeightTotal Weight

Valid (total weight(<C)

Invalid (total weight>C)

10+455515+2035Valid
10+607015+3045Valid
10+9010015+4055Valid
45+6010520+3050Valid
45+9013520+4060Valid
60+9015020+4070Valid
10+45+6011520+4065Valid
10+60+9016020+4085Invalid
10+45+9014520+4075Valid

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));      }}`