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.

# cook your dish here
*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][2]<=W):
  •        time+=ar[x][2]
  •        ans+=ar[x][1]
  • 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.

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.