The strategy am using is to pick the the next maximum cost values having weights of 1 and 2. Then adding it to m[i-1] and m[i-2] respectively. After which i take the maximum of both as m[i]. This analysis is correct right?
thanks a lot .it really helps .
Your code is not clear enough but what i think you are trying to do is to select items based on the heaviest seen and assume that will be part of optimal solution for knapsack. That is outright greedy selection and not the same type of greedy algorithm specified in the editorial. The type of greedy strategy specified in the tutorial was derived from the dynamic programming strategy for solving knapsack based on problem specification. If you need clarification email me arthurugochukwu@gmail.com
1 Like
Your Java code is not well indented but looking at it, its looks like O(M^2)
sryā¦got it ACā¦was using int intead of longā¦-_-ā¦realised after ālongā timeā¦
Can someone tell me why my solution is giving WA or provide the test case where it is giving WA?
Link to my Code
Code Explanation:
dp[i][0] = answer for capacity i
dp[i][1] = index upto which items of weight 1 have been used + 1
dp[i][2] = index upto which items of weight 2 have been used + 1
Rest should be easy enough for anybody to understand.
i got correct in this case but i am getting tle
I used greedy strategy of selecting maximum cost per unit weight i am getting correct in all test cases in this forum bu still getting TLE
Thanksā¦ for this test caseā¦ I have found my mistakeā¦
can anyone tell me for which testcase s my code is failing
https://www.codechef.com/viewsolution/30688688