susi_45
Feb '24

This is well known 0/1 knapsack problem. A O(n*w) algorithm is getting timed out as n and w is of order 10^5. Is there any more efficient approach to this kind of problems?

  • created

    Feb '24

  • last reply

    Mar '24
  • 1

    reply

  • 323

    views

  • 1

    user

susi_45
Mar '24

After AC…

This problem can be simplified as only two Koalas are required. This is not exact solution but a hint towards solution

Step 1: Sort array by weight
Step 2: Keep track of maximum beauty as per new array
Step 3: Compute max beauty possible for each koala as a pair