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 5Output:
4Solution:
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