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.
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 01 Knapsack and DP is required to solve & faster.