Potter and Profit

Posted: 28 Dec, 2020
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

There is a potter who makes pottery wares. With his saving, he can purchase some pottery clay, say ‘K’ units to make pottery wares. He can transform this clay into ‘N’ different items. Each item requires a certain amount of day for production. From past experiences, he knows the profit he will make on each item. he wishes to maximize the profit.

Given the amount of clay he has, the number of things that can be made, the days required, and the profit associated with items. Help him find the maximum profit that he can earn.

Input format :
The very first line contains an integer ‘T’ which denotes the number of test cases.

The first line of each test case contains two space-separated integers, ‘N’ and ‘K’, where ‘N’ is the number of things that can be made and ‘K’ is the number of units of clay he has.

The second line of each test case contains ‘N’ integers, where each integer denotes the number of units of clay required for that item.

The third line of each test case contains ‘N’ integers, where each integer denotes the amount of profit the potter can get if that item gets sold out.
Output Format :
For every test case,
Return the maximum profit the potter can make in a new line.
Note :
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 100  
1 <= N <= 100 
1 <= K <= 100 
1 <= profit[i] <= 10000 
1 <= Clay[i] <= 2000
Where ‘T’ is the number of test cases , ‘N’ is the number of integers , ‘K’ is the number of units of clay ,Clay[i] is the amount of clay used to build that ith item.

Time Limit: 1sec
Approach 1

We don’t know whether after picking the first item we will reach an optimal solution. It may happen that this item costs too much and its profit is not much, or an item can cost very less with higher profit. Another case could be, an item is costing too much, but then it is providing good profit as well. So we cannot determine whether it is beneficial to take it or not. Hence we will generate two recursive calls. One call in which we take it, and in the other, we leave it. From whichever option we receive the maximum profit, we will return that.


 

Algorithm:


 

  • Make two recursive calls
    • The first call is in which we take the item, and add its profit to our answer
    • In the second call, we leave that item and don’t add it to our profit
  • Now we have two options, whichever is maximum, we will return it.
  • Base cases can be
    • If a number of units of clay i.e ‘K’ become less than 0, which means we cannot pick anything, then we will return.
    • If we reach the end of the items list, we will return.

 


 

Try Problem