change.c
1.53 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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
#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
#include <errno.h>
#include <ctype.h>
#include <string.h>
#include "fdc_int.h"
#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);
for (i = 1; i < argc; ++i)
if (!strcmp(argv[i], "--all"))
one_solution = 0;
else if (isdigit(*argv[i]))
am = atoi(argv[i]);
else
fd__error("%s: unknown argument `%s'\n", argv[0], argv[i]);
for (i = 0; i < NCOINS; ++i)
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
printf("inconsistent CSP\n");
fd_end();
return !solutions;
}