# UVa 11259 - Coin Changing Again

This took lot of my time and I managed to come up with this Top-down Dynamic Programming solution. This approach times out. Any suggestions? Problem Statement : http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2226
`# include <cstdio># include <map># include <set>using namespace std;struct State{ State (int v1, int v2, int v3, int v4) {  V1 = v1; V2 = v2; V3 = v3; V4 = v4; } int getPart2(int Value = 0) {  int Part2 = 0;  Part2 = (V4 >> 13);  Part2 |= (Value << 4);  return Part2; } unsigned long long getPart1() {  unsigned long long Part1 = 0;  Part1 = V1;  Part1 |= (V2 << 17);  Part1 |= ((unsigned long long)V3 << 34);  Part1 |= ((unsigned long long)V4 << 51);  return Part1; } int V1, V2, V3, V4;};map <int, set<unsigned long long> > States;map <int, set<unsigned long long> > Solutions;int c1, c2, c3, c4, q, d1, d2, d3, d4, v;unsigned long long Result ;bool CheckVisited (unsigned long long Part1, int Part2){ if (States[Part2].count (Part1)) return true; States[Part2].insert (Part1); return false;}void Solution (State & s, int Value){ unsigned long long Part1 = s.getPart1(); int Part2 = s.getPart2(Value); if (!Value) {  Solutions[Part2].insert (Part1);  return; } if (CheckVisited(Part1, Part2)) return; if (s.V1 - 1 >= 0 && Value - c1 >= 0) {  s.V1--;  Solution (s, Value - c1);  s.V1++; } if (s.V2 - 1 >= 0 && Value - c2 >= 0) {  s.V2--;  Solution (s, Value - c2);  s.V2++; } if (s.V3 - 1 >= 0 && Value - c3 >= 0) {  s.V3--;  Solution (s, Value - c3);  s.V3++; } if (s.V4 - 1 >= 0 && Value - c4 >= 0) {  s.V4--;  Solution (s, Value - c4);  s.V4++; }}int main(){ freopen ("Input.txt", "r", stdin); freopen ("Scratch.txt", "w", stdout); int N; scanf ("%d", &N); State s (0, 0, 0, 0); while (N--) {  scanf ("%d%d%d%d%d", &c1, &c2, &c3, &c4, &q);  while (q--)  {   scanf ("%d%d%d%d%d", &s.V1, &s.V2, &s.V3, &s.V4, &v);   Result = 0;   States.clear();   Solutions.clear();   Solution (s, v);   for (map<int, set<unsigned long long> >::iterator it = Solutions.begin(); it != Solutions.end(); it++)    Result += it->second.size();   printf ("%lld\n", Result);  } }}`

# Number of Ways to Change Making (Dynamic Programming)

This is a variant of change making problem. Here, we are just asked to count the number of ways to make the specific change. With a little change to the change making problem's solution, we can solve this one. The problems which can be solved with the following solution are
`UVa - 657 - Coin ChangeUVa - 357 - Let Me Count The Ways (Need to change the way solution is printed as per problem description)`
`# include <iostream># include <cstdio>using namespace std;unsigned long long NumberOfWays [30001], Coins []= {1, 5, 10, 25, 50}, Num;int main (){ //freopen ("Input.txt", "r", stdin); //freopen ("Scratch.txt", "w", stdout); NumberOfWays[0] = 1; for (int i = 0; i < 5; i++)  for (int j = Coins[i]; j < 30001; j++)   NumberOfWays [j] += NumberOfWays [j - Coins[i]]; while (scanf ("%lld", &Num) != EOF)  printf ("%lld\n", NumberOfWays[Num]); //Change this for UVa - 357 - Let Me Count The Ways}`

# Change Making (Dynamic Programming) Problem

This is a classic change making problem.
A variant of the same problem, counting the number of ways to make the change is here
`Problem Name : Making ChangeProblem ID   : 2768Problem URL  : http://acm.tju.edu.cn/toj/showp2768.htmlSolution     :`
`# include <iostream># include <cstdio># include <cstring># include <algorithm>int denoms [10];int change [1001];using namespace std;int main(){ //freopen ("Input.txt", "r", stdin); //freopen ("Scratch.txt", "w", stdout); int C, N; scanf ("%d%d", &C, &N); fill (change, change + C + 1, 10000); for (int i = 0; i < N; i++) scanf ("%d", &denoms[i]); sort (denoms, denoms + N); change[0] = 0; for (int j = 0; j < N; j++)  for (int i = denoms[j]; i <= C; i++)   change[i] = min (change[i], change[i - denoms[j]] + 1); printf ("%d\n", change[C]);}`

# Installing Python-ldap in Ubuntu

These are the steps to be followed to install python-ldap in Ubuntu. At first,
`sudo apt-get install python-ldap`
would throw the following error
`In file included from Modules/LDAPObject.c:4:0:Modules/common.h:10:20: fatal error: Python.h: No such file or directory compilation terminated.error: command 'gcc' failed with exit status 1`
To get past this error, we need to install python-dev package
`sudo apt-get install python-dev`
After installing that we ll get the following error
`In file included from Modules/LDAPObject.c:9:0:Modules/errors.h:8:18: fatal error: lber.h: No such file or directorycompilation terminated.`
To get past this error, we need to install ldap2-dev package
`sudo apt-get install libldap2-dev`
After installing that we ll get the following error
`Modules/LDAPObject.c:18:18: fatal error: sasl.h: No such file or directory compilation terminated.error: command 'gcc' failed with exit status 1`
To get past this error, we need to install libsasl2-dev package
`sudo apt-get install libsasl2-dev`
After that
`sudo apt-get install python-ldap`
should install python-ldap without any problems.