Wa on all test cases

#1


I have done it as both 0-1 knap and N knapsack problem but I cant get the write ans, I am not able to figure out my mistake

#2

Hey @Krishna-Singh-2678805765519156
This problem is can be reduced to 0-1 Knapsack Problem. So in cost array, we first ignore those packets which are not available i.e; cost is -1 and then traverse the cost array and create two array val[] for storing cost of ‘i’ kg packet of orange and wt[] for storing weight of corresponding packet. Suppose cost[i] = 50 so weight of packet will be i and cost will be 50.
Algorithm :

  • Create matrix min_cost[n+1][W+1], where n is number of distinct weighted packets of orange and W is maximum capacity of bag.
  • Initialize 0th row with INF (infinity) and 0th Column with 0.
  • Now fill the matrix
    • if wt[i-1] > j then min cost[i][j] = min cost[i-1][j] ;
    • if wt[i-1] <= j then min cost[i][j] = min(min cost[i-1][j], val[i-1] + min_cost[i][j-wt[i-1]]);
  • If min cost[n][W]==INF then output will be -1 because this means that we cant not make make weight W by using these weights else output will be min cost[n][W].
#3

I know the logic I have implemented it using that only but still not showing correct ans. why? can you tell why my code is wrong.

#4

Re-read the algo and then your code you will see the difference

#5

I have read it. Can you find the error?

#6

Hey @Krishna-Singh-2678805765519156
Sorry my bad ,I was reading your 1st function ,2nd function looks good ,I cant find any error in it.
Some other TA will look into it :slight_smile:

1 Like
#7

Can you tell when the other TA will respond?

#8

Hey @Krishna-Singh-2678805765519156
I am not sure ,I already passed your doubt

#9

@Krishna-Singh-2678805765519156
If you read the problem statement carefully then you will realise that the N value given in input does not represent the size of the array. Infact it is quite useless.
This is a 1D DP problem. The size of the array is W only , not N.
I am sharing my code snippet for reference. It is a fairly simple approach and I think it is self explanatory. Kindly refer to it and let me know if you need any further help regarding it.

#define lli long long int

lli buyOrangesBottomUp(lli *price,lli w){
    lli dp[w+1];
    dp[0] = 0;
    for(lli i=1; i<=w; i++) {
        dp[i] = price[i];
    }

    for(lli i=2;i<=w;i++){
        for(lli j=0;j<i;j++) {
	        if(price[i-j] == -1  || dp[j] == -1){
			    continue;
			}
            if(dp[i] == -1)
                dp[i] = dp[j] + price[i-j];
            else
                dp[i] = min(dp[i], dp[j] + price[i-j]);
        }
    }

  //  for(int i=1;i<=w;i++)   cout << dp[i] << " "; 
    return dp[w];
}
#10

this code gives wa even for the sample case

#11

@Krishna-Singh-2678805765519156
Just tried it. Passed all testcases for me.
Here’s the full code - https://ide.codingblocks.com/s/344731
I tried it on this problem - https://hack.codingblocks.com/app/contests/1737/426/problem

#12

hello @Krishna-Singh-2678805765519156 what is the problem that you are facing ?
because @tarunluthra has already provided you with the solution code .
also if you want the 2d dp code for this question .
here for your reference i am attaching it here .


if you feel that you dont understand anythin please ask here we will cleare your doubt .
Happy Learning !!

#13

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.