Advertisement
r57shell

Untitled

Dec 19th, 2013
108
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdio>
  2. #include <cstring>
  3.  
  4. int m;
  5. int min;
  6. int n;
  7. int coins[1000];
  8. int cur[100000];
  9. int result[100000];
  10. void sub(int s,int k)
  11. {
  12.  if (s > m)
  13.    return;
  14.  if (s == m)
  15.  {
  16.   if (min > k)
  17.   {
  18.      min = k;
  19.      memcpy(result, cur, k*sizeof(int));
  20.   }
  21.   return;
  22.  }
  23.  for (int i=0; i<n; ++i)
  24.  {
  25.      cur[k] = coins[i];
  26.      sub(s+coins[i],k+1);
  27.  }
  28. }
  29.  
  30. void main()
  31. {
  32.  scanf("%d %d",&n, &m);
  33.  for (int i=0; i<n; ++i)
  34.    scanf("%d", coins[i]);
  35.  min = 1000000;
  36.  sub(0,0);
  37.  for (int i=0; i<k; ++i)
  38.    printf("%d, ",result[i]);
  39. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement