Problem: PPTEST Problem - CodeChef
My Solution: CodeChef: Practical coding for everyone
AC Solution: CodeChef: Practical coding for everyone
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 0-1 Knapsack and DP is required to solve & faster.