I think the test case limit on Ck is very loose.
The limit is given upto 109, but the costs can be stored in an int variable!
@eashaaniitkgp this problem can be solved by greedy approach since, the weight in this problem is either 1 or 2. If you have variable weight then you cannot solve this problem by Greedy algorithm.
1 Like
For all those who are getting confused about how a greedy strategy worked here:
Actually, if you look carefully, the answer is hidden in the weight values of each object. In the actual knapsack problem, we have to check upon many previous values due to no bound on the weights.
But here, as can be seen, the weight can take only two values, i.e, 1 and 2. Hence, to ascertain the optimal answer for a bag of capacity C, we have to check only two consecutive previous values (because the current total weight i can be achieved only by : (i-1)+1 or (i-2)+2). Hence, only 2 variables storing the previous values are required, hence taking O(1) space, excluding the input storage.
3 Likes
Good day everyone please i would really be glad to know which test case my solution failed on or any error in my code here. I’ve been working on it throughout the night and still getting WA
http://www.codechef.com/viewsolution/4136882
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?
hi…everyone
we can solve this problem simply by dividing the query x<=m by
just assuming x as x=y+2 for y=x-2 which is previously calculated.
for even numbers start with 0. After that start with 2,4,6…as 0+2,2+2,4+2…Now the
answer is highest cost for y and 2, highest cost for y is previously calculated and
for 2 the answer is either cost of 1weight+1weight or 2weight items which have maximum cost
among the remaining. Likewise for odd queries also, starting with 1,1+2,3+2,5+2…
But I am getting WRONG ANSWER …can somebody correct me if i am wrong.
My code as per above idea:http://www.codechef.com/viewplaintext/4137370
thanks a lot .it really helps .
I am not good at dynamic programming but I wanted to ask if the below given approach is correct or not.
Approach:
Just Sort the W(weight) and C(cost) according to C and then
for(i=1;i<=sum;i++) {
ll C = i,j,ans=0;
for(j=n-1;j>=0;j--) {
if(C >= (P[j].w)){
C -= (P[j].w);
ans += (P[j].c);
}
}
printf("%lld ",ans);
}
Where sum : Total of Weight give i.e value of M
n : N in problem
and P is structure containing Weight (W) and Cost ©
Thank you.
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 [email protected]
1 Like
Your Java code is not well indented but looking at it, its looks like O(M^2)
Is this fractional knapsack problem?
Hey can anyone plz tell me why my code is showing a runtime error …whlie it runs perfactly on my local machine…http://www.codechef.com/viewsolution/4177710
hello everyone, I have tried a no. of test cases and my code gives the right answer but I am getting WA on submission. Can anyone plz tell me the test cases where my code is failing…http://www.codechef.com/viewsolution/7476633