Knapsack
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

Question

Knapsack

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

Accepted Answer

This was a direct application of 0-1 knapsack problem. So dynamic programming approach of knapsack was applied to this problem.
We built the 2d array in bottom up manner.

Accepted Answer

Brute Force

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.

Space Complexity: O(1)Explanation:

O(1)

Since we have not used up any additional space, complexity stays constant.

Time Complexity: O(2^n)Explanation:

O(2^N)

Where ‘N’ is the number of items. Since we are making two recursive calls each time, these recursive calls will grow exponentially.

Accepted Answer

DP

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.

Space Complexity: O(n^2)Explanation:

O(N*K)

As we are creating a 2-D array of N*K size.

Time Complexity: O(n^2)Explanation:

O(N*K)

Since the size of our array is N*K, thus a maximum number of calls will be N*K.

C++ (g++ 5.4)

/*

    Time Complexity     :   O(N * K)

    Space Complexity    :   O(N * K)



    Where 'N' is the number of elements and 'K' is the total time.

*/



int getMaxProfit(vector &time, vector &profit, int n, int k) {

    int i, w;

    vector> dp(n + 1, vector(k + 1));

 

    // Build table 'dp' in bottom up manner.

    for (i = 0; i <= n; i++) {

        for (w = 0; w <= k; w++) {

            if (i == 0 || w == 0) {

                dp[i][w] = 0;

            }

            else if (time[i-1] <= w) {

                dp[i][w] = max(profit[i-1] + dp[i - 1][w - time[i-1]], dp[i - 1][w]);

            }

            else {

                dp[i][w] = dp[i - 1][w];

            }

        }

    }



    return dp[n][k];

}

Python (3.5)

'''

    Time Complexity     :   O(N * K)

    Space Complexity    :   O(N * K)



    Where 'N' is the number of elements and 'K' is the total time.

'''



from typing import List





def getMaxProfit(time: List[int], profit: List[int], n: int, k: int) -> int:

    i, w = 0, 0

    dp = [[0 for i in range(k + 1)] for j in range(n + 1)]



    # Build table 'dp' in bottom up manner.

    for i in range(n + 1):

        for w in range(k + 1):

            if i == 0 or w == 0:

                dp[i][w] = 0

            elif(time[i - 1] <= w):

                dp[i][w] = max(profit[i-1] + dp[i - 1]

                               [w - time[i-1]], dp[i - 1][w])



            else:

                dp[i][w] = dp[i - 1][w]



    return dp[n][k]

Java (SE 1.8)

/*

    Time Complexity     :   O(N * K)

    Space Complexity    :   O(N * K)



    Where 'N' is the number of elements and 'K' is the total time.

*/



import java.util.ArrayList;



public class Solution {

    public static int getMaxProfit(ArrayList time, ArrayList profit, int n, int k) {

        int i, w;

        int dp[][] = new int[n + 1][k + 1];

 

        // Build table 'dp' in bottom up manner.

        for (i = 0; i <= n; i++) {

            for (w = 0; w <= k; w++) {

                if (i == 0 || w == 0) {

                    dp[i][w] = 0;

                }

                else if (time.get(i-1) <= w) {

                    dp[i][w] = Math.max(profit.get(i-1) + dp[i - 1][w - time.get(i-1)], dp[i - 1][w]);

                }

                else {

                    dp[i][w] = dp[i - 1][w];

                }

            }

        }



        return dp[n][k];

    }

}

Accepted Answer

DP

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.

Space Complexity: O(n)Explanation:

O(K)

As we are creating a 1-D array of K size.

Time Complexity: O(n^2)Explanation:

O(N*K)

Since the size of our array is N*K, thus a maximum number of calls will be N*K.

Python (3.5)

'''

    Time Complexity     :   O(N * K)

    Space Complexity    :   O(K)



    Where 'N' is the number of elements and 'K' is the total time.

'''



from typing import List





def getMaxProfit(time: List[int], profit: List[int], n: int, k: int) -> int:



    dp = [0 for i in range(k+1)]



    for i in range(1, n + 1):

        for w in range(k, -1, -1):

            if (time[i - 1] <= w):



                # Finding the maximum value.

                dp[w] = max(dp[w], dp[w - time[i - 1]] + profit[i - 1])



    # Returning the maximum value of knapsack.

    return dp[k]

Java (SE 1.8)

/*

    Time Complexity     :   O(N * K)

    Space Complexity    :   O(K)



    Where 'N' is the number of elements and 'K' is the total time.

*/



import java.util.ArrayList;



public class Solution {

    public static int getMaxProfit(ArrayList time, ArrayList profit, int n, int k) {

        int dp[] = new int[k + 1];



        for (int i = 1; i < n + 1; i++) {

            for (int w = k; w >= 0; w--) {

                if (time.get(i - 1) <= w) {



                    // Finding the maximum value.

                    dp[w] = Math.max(dp[w], dp[w - time.get(i- 1)] + profit.get(i - 1));

                }

            }

        }



        // Returning the maximum value of knapsack.

        return dp[k];

    }

}

C++ (g++ 5.4)

/*

    Time Complexity     :   O(N * K)

    Space Complexity    :   O(K)



    Where 'N' is the number of elements and 'K' is the total time.

*/



int getMaxProfit(vector &time, vector &profit, int n, int k) {

    vector dp(k + 1, 0);



    for (int i = 1; i < n + 1; i++) {

        for (int w = k; w >= 0; w--) {

            if (time[i - 1] <= w) {

                    

                // Finding the maximum value.

                dp[w] = max(dp[w], dp[w - time[i- 1]] + profit[i - 1]);

            }

        }

    }



    // Returning the maximum value of knapsack.

    return dp[k];

}

Accepted Answer

Gsushshsisbjss. eieheieheheoeh

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 :

Output Format :

Note :

Constraints :

Top Wipro Software Engineer interview questions & answers

Popular interview questions of Software Engineer

Top HR questions asked in Wipro Software Engineer