Blame view

bench/change.c 1.69 KB
965dadaa   Salvador Abreu   initial commit fr...
1
#include <stdio.h>
eef94371   Vasco Pedro   Update to PaCCS v...
2
#include <fcntl.h>
965dadaa   Salvador Abreu   initial commit fr...
3
4
5
6
7
8
9
#include <errno.h>
#include <ctype.h>
#include <string.h>

#include "fdc_int.h"

// try to save on variables
965dadaa   Salvador Abreu   initial commit fr...
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
static fd_int fd_const[MAX_VALUE + 1];

#define FD_CONST(n) (fd_const[n] ? fd_const[n] : (fd_const[n] = fd_new(n, n)))

//#define FD_CONST(n) fd_new(n, n)

#define NCOINS (sizeof(coins_value) / sizeof(*coins_value))

int coins_value[] = { 1, 2, 5, 10, 20, 50 };

int main(int argc, char *argv[])
{
  int solutions = 0, one_solution = 1;
  fd_int change[NCOINS], coins[NCOINS];
  fd_int ncoins, amount;
  int am = 37;
  int i;

  fd_init(&argc, &argv);

eef94371   Vasco Pedro   Update to PaCCS v...
30
  for (i = 1; i < argc; ++i)
965dadaa   Salvador Abreu   initial commit fr...
31
32
    if (!strcmp(argv[i], "--all"))
      one_solution = 0;
eef94371   Vasco Pedro   Update to PaCCS v...
33
    else if (isdigit(*argv[i]))
965dadaa   Salvador Abreu   initial commit fr...
34
35
36
37
      am = atoi(argv[i]);
    else
      _fd_error("%s: unknown argument `%s'\n", argv[0], argv[i]);

eef94371   Vasco Pedro   Update to PaCCS v...
38
  for (i = 0; i < NCOINS; ++i)
965dadaa   Salvador Abreu   initial commit fr...
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
    coins[i] = FD_CONST(coins_value[i]);

  for (i = 0; i < NCOINS; ++i)
    change[i] = fd_new(0, MAX_VALUE);

  amount = FD_CONST(am);
  fd_knapsack2(change, coins, NCOINS, amount);

  ncoins = fd_new(0, MAX_VALUE);
  fd_sum2(change, NCOINS, ncoins);

  fd_min(ncoins);

  while (fd_solve() == FD_OK)
    {
      printf("solution %d:\n", ++solutions);

      printf("coins needed: %d\n", fd_var_value(ncoins));

      for (i = 0; i < NCOINS; ++i)
	{
	  printf("%d × %d ", fd_var_value(change[i]), fd_var_value(coins[i]));

	  if (i != NCOINS - 1)
	    putchar('+'), putchar(' ');
	}
      printf(" = %d\n", fd_var_value(amount));

#if !(defined(LOCAL_SEARCH) || defined(DISTRIBUTED_SOLVER))
      if (one_solution)
#endif
	break;
    }

  if (solutions)
    printf("%d solutions found\n", solutions);
  else