##
__Buying Apples!__

Link to the question : ABA12C

###
__HINT :__

This is a problem of unbounded knapsack.

We will maintain an array ans[ k+1 ] where the j th index stores the minimum money required to buy j kg of apples.

To find the optimal ans[ j ] , we need to decide whether to select or reject an instance of weight 'i'.

If we reject all the weights then ans[ j ] = price[ j ], and if we select 'i' then

ans[ j ] = minimum[ ans[j - i] + price[ i ] ] for i= 0,1....j-1.

You can look into the source code for a better understanding.

####
__RECOMMENDED QUESTION :__

Try your hands on this dp question : Morena

###
__SOLUTION :__

/* ABA12C - Buying Apples */ /* Sushant Gupta */ #include<bits/stdc++.h> using namespace std; int main() { int t; scanf("%d",&t); while(t--) { int n,k,b; scanf("%d%d",&n,&k); b =k; int p[k +1]; int i,j; for( i=1; i<=k; i++ ) scanf("%d",&p[i]); int ans[k+1]; for(i=1; i<=k; i++) { //if(p[i] == -1) // ans[i] = INT_MAX; //else ans[i] = p[i]; } for(i=2; i<=k; i++) { for(j=1; j<i; j++) { if(p[i-j] == -1 || ans[j] == -1) continue; if(ans[i] == -1) ans[i] = ans[j] + p[i-j]; else ans[i] = min(ans[i], ans[j] + p[i-j]); } } if(k==0) printf("0\n"); else printf("%d\n",ans[k]); } return 0; }

can you explain this line-- ans[ j ] = minimum[ ans[j - i] + price[ i ] ] for i= 0,1....j-1.

ReplyDeleteThis means that, for eg if I need to buy apples of weight 5kg, then to find ans[5] I have several options like buy 5 packets of 1 kg or buy 1 packet of 2kg and 1 of 3kg etc.

DeleteHence in order to find the best case, I run a loop from (i =0 to i<j) and find the combination which costs the minimum. So ans[j] will be minimum of either ans[j] , i.e, I do not choose the ith packet, or ans[j-i] + price[i], i.e, I have chosen the ith packet.

For further reading on unbounded knapsack, you can refer this site :

http://www.csegeek.com/csegeek/view/tutorials/algorithms/dynamic_prog/dp_part7.php

its wrong sol...u r not considering n anywhere which is the max amt of packets u can buy

ReplyDeletefor test case : 1 5 1 3 4 5 6 the ans should be 6 but ur code is giving 5.

Read the comments in the question. Many users have written that if they considered 'n' then they got a WA but without considering it their solution got AC.

DeleteHence, even I did not consider it.

Okay the complexity of this solution is K^2 right? In case we consider n, it will increase to O((K^2)*N) right?

ReplyDeleteYeah, I think the complexity should be O(k*k*n) although I have not tried it yet.

Deletecan you explain the line----->

ReplyDeleteif(p[i-j] == -1 || ans[j] == -1)

continue;