SPOJ: NOCHANGE

                                     

1847. No Change

Problem code: NOCHANGE

This is a dynamic programming problem. Here is O(k*x) based solution of this problem.

Equation : n1*v1+n2*v2...+nk*vk=x;

 where n1>=n2>=n3...>=nk;

Let ans[x+1] be a boolean array where ans[i] determines whether it is possible to pay money i. 

For coin of value v[0], we calculate ans[i] , if(i%v[0]==0) ans[i]=true  

OR

 in dp term  if(ans[i]==true||ans[i-v[0]]=true) ans[i]==true.

When we get an extra coin of value v[1], as per the constraints we have to pay at least as many coins of value v[0] as of value v[1].

now consider v[1]=v[1]+v[0] i.e a coin of value v[1]+v[0] .As per the equation we have considered n2 number of v1 coins and n2 number of v2 coins and for remaining n1-n2 coins of value v[0], we have already computed ans[i].

now if(ans[i]==true|| ans[i-v[1]]==true) ans[i]=true;

Similar is the case when we consider ans[i] for coins of value v[2]...v[k].

e.g input 13 3 9 2 1.
after processing v[]={9,11,12};
base condition
ans[0]=true :as we can always pay money=0;
ans[i]=false : default (not computed)
ans
optimal substructure: ans[j]=ans[j] | ans[j-v[i]];

CODE:

#include<cstdio>
using namespace std;

int main()
{
 int x,k;
 scanf("%d %d",&x,&k);
 int v[k],i,j;
 for(i=0;i<k;i++)
   {scanf("%d",&v[i]);
  if(i>0)
   v[i]+=v[i-1];
   }

 bool ans[x+1];
//base condition
    ans[0]=true;
  for(i=1;i<=x;i++)
     ans[i]=false;

  for(i=0;i<k;i++)
   {
    for(j=v[i];j<=x;j++)
 {
   ans[j]|=ans[j-v[i]];  
 }
   }
 if(ans[x])printf("YES\n");
 else printf("NO\n");
 return 0;
}