Last Updated: 28 Dec, 2020
Potter and Profit
Easy
Asked in companies
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
Approaches
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.
The idea here is the same, we will make two function calls, but this time we will try to reduce the repetitive calls by using a 2-D array.
In this array, the number of rows denotes the number of items, and the column number denotes the maximum units of clay we have. We can use memoization.
Algorithm :
- Create a 2-D array, and initialize it with -1.
- Generate two recursive calls, in which we take one item/leave one item.
- Save the answer in our 2-D array, and return the answer.
- Whenever we receive the values of ‘K’ and ‘N’ that are already stored in the array, we won’t call any further, and return the stored answer.
The recursion tree is for the following sample input.
Clay[] = {1, 1, 1}, K = 2, Profit[] = {10, 20, 30}
(n, K)
(3, 2)
/ \
/ \
(2, 2) (2, 1)
/ \ / \
/ \ / \
(1, 2) (1, 1) (1, 1) (1, 0)
/ \ / \ / \
/ \ / \ / \
(0, 2) (0, 1) (0, 1) (0, 0) (0, 1) (0, 0)
Recursion tree for Knapsack capacity 2
units and 3 items of 1 unit weight. Here we can see the repetitive calls.
The idea here is the same, we will make two function calls, but this time we will try to reduce the repetitive calls by using a 1-D array.
In this array, the elements denote the maximum profit we can have
Algorithm :
- Create a 2-D array, and initialize it with -1.
- Generate two recursive calls, in which we take one item/leave one item.
- Save the answer in our 2-D array, and return the answer.
- Whenever we receive the values of ‘K’ and ‘N’ that are already stored in the array, we won’t call any further, and return the stored answer.
this is the case where we used 2-D array but,
We don’t require all the elements of a 2-D array at the same time, so we will try to maintain a 1-D array, and then delete this array, and create another one. The maximum size of the array will be ‘K’. All we need to do is make all the changes in the same 1-D array. Since in each iteration, we don’t actually require the rest of the elements.
Similar problems