Another constraint between sets and integers is the weight/3 constraint. It allows the association of weights to set elements, and can help when solving problems of the knapsack or bin packing type. The constraint takes a set and an array of element weights and constrains the weight of the whole set:
?- ic_sets:(Container :: [] .. [1, 2, 3, 4, 5]),
Weights = [](20, 34, 9, 12, 19),
weight(Container, Weights, W).
Container = Container{([] .. [1, 2, 3, 4, 5]) : _2127{0 .. 5}}
Weights = [](20, 34, 9, 12, 19)
W = W{0 .. 94}
There is 1 delayed goal.
Yes (0.01s cpu)
By adding a capacity limit and a search primitive, we can solve a knapsack problem:
?- ic_sets:(Container :: [] .. [1, 2, 3, 4, 5]), Weights = [](20, 34, 9, 12, 19), weight(Container, Weights, W), W #=< 50, insetdomain(Container,_,_,_). Weights = [](20, 34, 9, 12, 19) W = 41 Container = [1, 3, 4] More (0.00s cpu)
By using the heuristic options provided by insetdomain, we can implement a greedy heuristic, which finds the optimal solution (in terms of greatest weight) straight away:
?- ic_sets:(Container :: [] .. [1, 2, 3, 4, 5]), Weights = [](20, 34, 9, 12, 19), weight(Container, Weights, W), W #=< 50, insetdomain(Container,decreasing,heavy_first(Weights),_). W = 48 Container = [1, 3, 5] Weights = [](20, 34, 9, 12, 19) More (0.00s cpu)
- weight(?Set, ++ElementWeights, ?Weight)
- According to the array of element weights, the weight of set Set1 is Weight
Figure 10.5: Set Weight Constraint