Get a guaranteed software dev job of ₹5-40 LPA | Apply now for free!

Nagarro Question Solved | Literary Competition | Codewindow.in

Question:

In a literary competition, children are asked to read books from a set of N different books. A child takes some time to read a book and after finishing that book. he/she is awarded with some points which can later be redeemed for gifts. The Competition has a time limit T.

Your task is to design a strategy that helps the child in earning maximum points by reading any number of books, with a constraint that total reading time of the selected books should not exceed the time limit T of the competition.

 

Input Specification:

input 1: An integer N depending the number of books

input 2: An integer T denoting the time limit of the competition where T<=160

input 3: An integer array of N elements where each value of the array represents the number of points awarded for reading the ith book(where, 0<=i<=N-1 and 1<=input4[i]<=100)

Output Specifications:

Return the maximum points a child can earn.

 

Example 1:

Input1: 3

Input2: 7

Input3: 2 6 9

Input4: 3 5 3

Output: 11

Explanation:

The child will read the 0th and the 2nd book as time required by them is 3 +3=6 which as

less than 7 ( the time limit of competition) thus amounting to 2 +9 =11 points. Therefore, 11 will be returned as the output.

 

Example 2:

input1: 2

input2: 5

input3: 2 4

input4: 3 5

Output: 4

Explanation:

The child will only be able to read the 1st book as time required to read it is 5 which is equal to 5 (time limit of the competition) thus awarding him 4 points, Therefore 4 will be returned as the output.

 

Input:

2
5
2 4
3 5

Output:

4

Solution:

Python :

#https://codewindow.in
#join or telegram channel @codewindow

def CalculateTime(W, wt, val, n):
    if n == 0 or W == 0:
        return 0

    if (wt[n-1] > W):
        return CalculateTime(W, wt, val, n-1)
    else:
        return max(val[n-1] + CalculateTime(W-wt[n-1], wt, val, n-1), CalculateTime(W, wt, val, n-1))



n = int(input())
W = int(input())
val = list(map(int, input().split(" ")))
wt = list(map(int, input().split(" ")))
print(CalculateTime(W, wt, val, n))

C++ :

//https://codewindow.in
//join or telegram channel @codewindow

#include <bits/stdc++.h>
#include <iostream>
using namespace std;

int max(int a, int b) { return (a > b) ? a : b; }

int knapSack(int W, int wt[], int val[], int n)
{
    if (n == 0 || W == 0)
        return 0;

    if (wt[n - 1] > W)
        return knapSack(W, wt, val, n - 1);
    else
        return max(val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1), knapSack(W, wt, val, n - 1));
}

int main()
{
    int n;
    cin >> n;
    int W;
    cin >> W;
    int val[n];
    int wt[n];
    for(int i=0;i<n;i++)
        cin >> val[i];
    for(int i=0;i<n;i++)
        cin >> wt[i];
    cout << knapSack(W, wt, val, n);
    return 0;
}

JAVA :

//https://codewindow.in
//join or telegram channel @codewindow

import java.util.*;
import java.lang.*;
import java.io.*;

class CodeWindow
{
    static int max(int a, int b)
    {
      return (a > b) ? a : b;
    }
    static int calculateTime(int W, int wt[], int val[], int n)
    {
        if (n == 0 || W == 0)
            return 0;
        if (wt[n - 1] > W)
            return calculateTime(W, wt, val, n - 1);
        else
            return max(val[n - 1] + calculateTime(W - wt[n - 1], wt, val, n - 1), calculateTime(W, wt, val, n - 1));
    }

    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int W = sc.nextInt();
        int val[] = new int[n];
        int wt[] = new int[n];
        for(int i=0;i<n;i++)
            val[i] = sc.nextInt();
        for(int i=0;i<n;i++)
            wt[i] = sc.nextInt();
        System.out.println(calculateTime(W, wt, val, n));
    }
}

Also Checkout

Recent Posts