I dont know why getting wrong ans

#1

https://codeforces.com/contest/1447/submission/99389175

please tell me why i am getting wrong ans in the first test case as the sum is 6 but showing me 22 how?

and please check if there is any mistake in my code

#2

Hey @shivamgoel150 first test case is:
1 3
3
How sum is 6?
In the first test case, we can take the item of weight 3 and fill the knapsack just right.
Elaborate your doubt.

#3

n=7 w=12 and a[]=1 1 1 17 1 1 1 in this its is saying that sum is 22

#4

see the test details of my submission

#5

Don’t look at checker comment, as half of the logic you have used is right but another half is not. Let me help you in pointing out mistake of your logic

You took input n & w , that is 7 & 12

  • Calculated min as 6 (12/2)
  • Have stored elements in v[i] and they are
    1 1 1 17 1 1 1
  • And then you sort vector v, which gives you resulting vector
    1 1 1 1 1 1 17

Till now everything is good

Now after that what you are doing is storing sum of every element and storing the jndexes in vector a, and if the sum reaches to a state where your sum >= min and sum<=w you are printing it. And you get indexes from 1 to 6 comprising of all six one’s. That’s why you are getting output as ( 1 2 3 4 5 6 )
This is wrong, instead do what

  • Make pair of int and index value. Store them in a vector of pairs of int and index value. Sort this vector in ascending order of their int values and you will get a vector of pair like this
    {(1,1); (1,2); (1,3); (1,5); (1,6); (1,7); (17,4)}
  • After doing this itertate from back of this array and see this condition which you were seeing earlier that your sum >= min and sum<=w so when you will do this you will go on 17 which will give you a false, so now you reach to 1 of 7th index you add 1 to sum, add index 7 in an array a, now you reach to 1 of 6th index you add 1 to sum, add index 6 in an array a, now you reach to 1 of 5th index you add 1 to sum, add index 5 in an array a, now you reach to 1 of 3rd index you add 1 to sum, add index 3 in an array a, and so on till you go to last one of index 1
  • so you will be having
    7, 6, 5, 3, 2 & 1 in your array a
    Print this and you will get your answer. Still have a doubt, feel free to ask.
#6

Here’s the same implementation I have given to you https://ide.codingblocks.com/s/378179
If have any issue , feel free to ask. If your doubt is solved then mark it as resolved.

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.