Count the coins/0-1: Difference between revisions
Content added Content deleted
(Removed superfluous 'the'. Perl entry no longer shows an example but Raku does.) |
(Realize in MiniZinc) |
||
| Line 27: | Line 27: | ||
* Show an example of coins you used to reach the given sum and their indices. See Raku for this case. |
* Show an example of coins you used to reach the given sum and their indices. See Raku for this case. |
||
=={{header|MiniZinc}}== |
|||
; coins = [1, 2, 3, 4, 5] and sum = 6 |
|||
<lang MiniZinc> |
|||
%Subset sum. Nigel Galloway: January 6th., 2021. |
|||
enum Items={a,b,c,d,e}; |
|||
array[Items] of int: weight=[1,2,3,4,5]; |
|||
var set of Items: selected; |
|||
var int: wSelected=sum(n in selected)(weight[n]); |
|||
constraint wSelected=6; |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
selected = {a, b, c}; |
|||
---------- |
|||
selected = {a, e}; |
|||
---------- |
|||
selected = {b, d}; |
|||
---------- |
|||
========== |
|||
%%%mzn-stat: initTime=0 |
|||
%%%mzn-stat: solveTime=0.001 |
|||
%%%mzn-stat: solutions=3 |
|||
%%%mzn-stat: variables=21 |
|||
%%%mzn-stat: propagators=31 |
|||
%%%mzn-stat: propagations=236 |
|||
%%%mzn-stat: nodes=11 |
|||
%%%mzn-stat: failures=3 |
|||
%%%mzn-stat: restarts=0 |
|||
%%%mzn-stat: peakDepth=3 |
|||
%%%mzn-stat-end |
|||
Finished in 172msec |
|||
</pre> |
|||
; coins = [1, 1, 2, 3, 3, 4, 5] and sum = 6 |
|||
<lang MiniZinc> |
|||
%Subset sum. Nigel Galloway: January 6th., 2021. |
|||
enum Items={a,b,c,d,e,f,g}; |
|||
array[Items] of int: weight=[1,1,2,3,3,4,5]; |
|||
var set of Items: selected; |
|||
var int: wSelected=sum(n in selected)(weight[n]); |
|||
constraint wSelected=6; |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
selected = {a, b, f}; |
|||
---------- |
|||
selected = {a, c, d}; |
|||
---------- |
|||
selected = {a, c, e}; |
|||
---------- |
|||
selected = {a, g}; |
|||
---------- |
|||
selected = {b, c, d}; |
|||
---------- |
|||
selected = {b, c, e}; |
|||
---------- |
|||
selected = {b, g}; |
|||
---------- |
|||
selected = {c, f}; |
|||
---------- |
|||
selected = {d, e}; |
|||
---------- |
|||
========== |
|||
%%%mzn-stat: initTime=0 |
|||
%%%mzn-stat: solveTime=0.001 |
|||
%%%mzn-stat: solutions=9 |
|||
%%%mzn-stat: variables=29 |
|||
%%%mzn-stat: propagators=43 |
|||
%%%mzn-stat: propagations=820 |
|||
%%%mzn-stat: nodes=35 |
|||
%%%mzn-stat: failures=9 |
|||
%%%mzn-stat: restarts=0 |
|||
%%%mzn-stat: peakDepth=4 |
|||
%%%mzn-stat-end |
|||
Finished in 187msec |
|||
</pre> |
|||
; coins = [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100] and sum = 40 |
|||
<lang MiniZinc> |
|||
%Subset sum. Nigel Galloway: January 6th., 2021. |
|||
enum Items={a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p}; |
|||
array[Items] of int: weight=[1,2,3,4,5,5,5,5,15,15,10,10,10,10,25,100]; |
|||
var set of Items: selected; |
|||
var int: wSelected=sum(n in selected)(weight[n]); |
|||
constraint wSelected=40; |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
selected = {a, b, c, d, e, f, g, h, k}; |
|||
---------- |
|||
selected = {a, b, c, d, e, f, g, h, l}; |
|||
---------- |
|||
[ 0 more solutions ] |
|||
selected = {a, b, c, d, e, f, g, h, m}; |
|||
---------- |
|||
[ 1 more solutions ] |
|||
selected = {a, b, c, d, e, f, g, i}; |
|||
---------- |
|||
[ 3 more solutions ] |
|||
selected = {a, b, c, d, e, f, k, l}; |
|||
---------- |
|||
[ 7 more solutions ] |
|||
selected = {a, b, c, d, e, g, k, l}; |
|||
---------- |
|||
[ 15 more solutions ] |
|||
selected = {a, b, c, d, e, j, k}; |
|||
---------- |
|||
[ 31 more solutions ] |
|||
selected = {a, b, c, d, g, h, l, n}; |
|||
---------- |
|||
[ 63 more solutions ] |
|||
selected = {a, d, e, h, i, l}; |
|||
---------- |
|||
[ 127 more solutions ] |
|||
selected = {b, c, e, l, m, n}; |
|||
---------- |
|||
[ 206 more solutions ] |
|||
selected = {k, l, m, n}; |
|||
---------- |
|||
========== |
|||
%%%mzn-stat: initTime=0.001 |
|||
%%%mzn-stat: solveTime=0.011 |
|||
%%%mzn-stat: solutions=464 |
|||
%%%mzn-stat: variables=65 |
|||
%%%mzn-stat: propagators=91 |
|||
%%%mzn-stat: propagations=122926 |
|||
%%%mzn-stat: nodes=4203 |
|||
%%%mzn-stat: failures=1638 |
|||
%%%mzn-stat: restarts=0 |
|||
%%%mzn-stat: peakDepth=13 |
|||
%%%mzn-stat-end |
|||
Finished in 207msec |
|||
</pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
<lang perl>#!/usr/bin/perl |
<lang perl>#!/usr/bin/perl |
||