Message on Whatsapp 8879355057 for DSA(OA + Interview) + Fullstack Dev Training + 1-1 Personalized Mentoring to get 10+LPA Job
0 like 0 dislike
5,833 views
All past online assesments of TikTok can be found using the tag "tiktok_oa" in the search bar.

Here is the link :/https://www.desiqna.in/tag/tiktok_oa
in Online Assessments by Expert (35,210 points) | 5,833 views

1 Answer

0 like 0 dislike

Given a list of integers representing weights and a target number representing maximum capacity of knapsack, return the maximum weight the knapsack can hold.

 

example: inputs --> wt: [1,3,5], W= 7
output -> 6

 

example: inputs --> wt: [4,8,5,9], W= 20
output -> 18

 

static int knapSack(int W, List<Integer> wt)
    {
        int n = wt.size();
        // Base Case
        if (n == 0 || W == 0)
            return 0;

        // If weight of the nth item is
        // more than Knapsack capacity W,
        // then this item cannot be included
        // in the optimal solution
        if (wt.get(n-1) > W)
            return knapSack(W, wt.subList(0,n-1));

            // Return the maximum of two cases:
            // (1) nth item included
            // (2) not included
        else
            return Math.max(wt.get(n-1) + knapSack(W - wt.get(n-1), wt.subList(0,n-1)),
                    knapSack(W,wt.subList(0,n-1))
            );
    }
by Expert (35,210 points)