 # PPTEST without Knapsack Algorithm

Problem: Contest Page | CodeChef
My Solution: Solution: 41622207 | CodeChef
AC Solution: Solution: 41624998 | CodeChef

Here is my logic:
Do a Benefit to cost analysis to get Points/Time ratio and sort them in descending order. Then take the best cases first and iterate as long as we have waiting time to spare.

*for _ in range(int(input())):

• N,W = map(int,input().split())
• ar = []
• for x in range(N):
• ``````   c,p,t=map(int,input().split())
``````
• ``````   ar.append([(c*p)/t,c*p,t])
``````
• ar.sort(reverse=True)
• ans=0
• time=0
• for x in range(N):
• ``````   if(time+ar[x]<=W):
``````
• ``````       time+=ar[x]
``````
• ``````       ans+=ar[x]
``````
• print(ans)

I am trying to solve this question without using the Knapsack Algorithm. I have written a solution and tried many cases that give correct answers and I’ve verified the same from AC Solution codes. I am unable to figure out where is it going wrong/

I will continue to figure it out and in the meanwhile, if someone can help me out here it would be really helpful. Thanks

So, Here is an update. I have found a test case where it doesn’t satisfy.

1
3 20
1 3 18
1 2 2
1 2 10

Output: 4 (Wrong) 5 (Correct)

This is why Greedy doesn’t work always here in 0-1 Knapsack and DP is required to solve & faster.