Wednesday 2 March 2016

ABA12C

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;
}

10 comments:

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

    ReplyDelete
    Replies
    1. This 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.
      Hence 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

      Delete
  2. its wrong sol...u r not considering n anywhere which is the max amt of packets u can buy
    for test case : 1 5 1 3 4 5 6 the ans should be 6 but ur code is giving 5.

    ReplyDelete
    Replies
    1. 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.
      Hence, even I did not consider it.

      Delete
    2. How does that mean we have not found the answer yet?

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

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

      Delete
  4. can you explain the line----->
    if(p[i-j] == -1 || ans[j] == -1)
    continue;

    ReplyDelete
    Replies
    1. p[ i ] denotes the price of i kg apples. So as per the question p[i] can be equal to -1. ans[i] denotes the minimum to cost to buy i kg of apples. If ans[j] = -1, then that means that for the following j we have not found the answer yet. So in either of the cases let the for loop continue.

      Delete
  5. In your code, you write: ans[i] = min(ans[i], ans[j] + p[i-j]);
    I think it must be ans[i]=min(ans[i],ans[i-j]+p[j]);
    Although Both of them can be true, I think the second one is more comfortable.

    ReplyDelete