#include <iostream>
using namespace std;
//typedef long long int lint;
#define INF 1000000000
int dp[10001];
int coins(int wt,int a[],int v[],int n)
{
if(wt<0)
return INF;
if(wt==0)
return 0;
if(dp[wt]!=INF)
return dp[wt];
for(int i=0;i<n;i++)
{ int k=coins(wt-a[i],a,v,n);
if(v[i]+k<dp[wt])
dp[wt]=v[i]+k;
}
return dp[wt];
}
int main() {
ios_base::sync_with_stdio(false);
int t;
cin>>t;
while(t--)
{ int e,f;
cin>>e>>f;
int wt=f-e;
for(int i=0;i<wt+1;i++)
dp[i]=INF;
int n;
cin>>n;
int a[n],v[n];
for(int i=0;i<n;i++)
cin>>v[i]>>a[i];
int m=coins(wt,a,v,n);
if(m==INF)
cout<<"This is impossible.\n";
else
cout<<"The minimum amount of money in the piggy-bank is "<<m<<"."<<endl;
}
return 0;
}
Here is My AC solution to this problem. I have coded it very simple so that you can understand every part of it.
Have a look it might help you in figuring out your mistake .
Please either paste the code in the correct format or just provide the link on ideone or on codechef compiler .
thanks for the reply.I see you have used bottom-up approach .I converted my top-down approach to bottom up it got accepted.Does anyone know why?