/*
Subset sum problem in Comet.
From Katta G. Murty: "Optimization Models for Decision Making", page 340
http://ioe.engin.umich.edu/people/fac/books/murty/opti_model/junior-7.pdf
"""
Example 7.8.1
A bank van had several bags of coins, each containing either
16, 17, 23, 24, 39, or 40 coins. While the van was parked on the
street, thieves stole some bags. A total of 100 coins were lost.
It is required to find how many bags were stolen.
"""
This Comet model was created by Hakan Kjellerstrand (hakank@bonetmail.com)
Also, see my Comet page: http://www.hakank.org/comet
*/
import cotfd;
int t0 = System.getCPUTime();
int n = 6;
int total = 100;
int coins[1..n]= [16, 17, 23, 24, 39, 40];
Solver m();
var{int} x[1..n](m, 0..n);
var{int} ss(m, 0..n); // total number of bags stolen
//
// subset_sum(values, x, tot)
// where
// values is the values to choose from (the coin values)
// x contatins the resulting var
// total is the total value to sum
//
function void subset_sum(int[] values, var{int}[] x, int tot) {
Solver cp = x[1].getSolver();
cp.post(sum(i in x.rng()) (values[i]*x[i]) == tot);
}
Integer num_solutions(0);
exploreall {
m.post(ss == sum(i in 1..n) x[i]);
subset_sum(coins, x, total);
} using {
label(m);
num_solutions++;
cout << x << " ss: " << ss << endl;
}
// cout << x << endl;
cout << "\nnum_solutions: " << num_solutions << endl;
int t1 = System.getCPUTime();
cout << "time: " << (t1-t0) << endl;
cout << "#choices = " << m.getNChoice() << endl;
cout << "#fail = " << m.getNFail() << endl;
cout << "#propag = " << m.getNPropag() << endl;