Subset sum problem: Difference between revisions
Content added Content deleted
(→{{header|C}}: for listing all combos) |
m (→{{header|REXX}}: added whitespace, order subroutines in alphabetic order, added comments, changed comments, deleted superfluous semicolons. -- ~~~~) |
||
| Line 785: | Line 785: | ||
end /*chunk*/ |
end /*chunk*/ |
||
if ??==0 then ??='no' /* |
if ??==0 then ??='no' /*Englishise solutions number.*/ |
||
call tello 'Found' ?? "subset"s(??) 'whose summed weight's(??) "=" target |
call tello 'Found' ?? "subset"s(??) 'whose summed weight's(??) "=" target |
||
exit /*stick a fork in it, we done.*/ |
exit /*stick a fork in it, we done.*/ |
||
/* |
/*──────────────────────────────────COMBN subroutine────────────────────*/ |
||
combN: procedure expose @. #. ?? stopAt target; parse arg x,y; !.=0 |
combN: procedure expose @. #. ?? stopAt target; parse arg x,y; !.=0 |
||
base=x+1; bbase=base-y; ym=y-1 /*!.n are the combination digits*/ |
base=x+1; bbase=base-y; ym=y-1 /*!.n are the combination digits*/ |
||
do n=1 for y; !.n=n; |
do n=1 for y; !.n=n; end /*build 1st combination*/ |
||
do j=1; _=!.1; s=#._ /*get 1st dig & the sum*/ |
do j=1; _=!.1; s=#._ /*get 1st dig & the sum*/ |
||
if s>target then leave /*1st dig>target? Then we're done*/ |
if s>target then leave /*1st dig>target? Then we're done*/ |
||
do k=2 for ym; _=!.k; s=s+#._ |
do k=2 for ym; _=!.k; s=s+#._ /*Σ the weights; is sum > target?*/ |
||
if s>target then do; if .combUp(k-1) then return; iterate j; end |
if s>target then do; if .combUp(k-1) then return; iterate j; end |
||
end |
end /*k*/ |
||
if s==target then call telly /*found a pot of gold? */ |
if s==target then call telly /*found a pot of gold? */ |
||
!.y=!.y+1; if !.y==base then if .combUp(ym) then leave /*bump dig*/ |
!.y=!.y+1; if !.y==base then if .combUp(ym) then leave /*bump dig*/ |
||
end |
end /*j*/ |
||
return /*done with this combination set.*/ |
return /*done with this combination set.*/ |
||
/*──────────────────────────────────.combUp subroutine──────────────────*/ |
|||
.combUp: procedure expose !. y bbase; parse arg d; if d==0 then return 1 |
.combUp: procedure expose !. y bbase; parse arg d; if d==0 then return 1 |
||
p=!.d; do u=d to y; !.u=p+1 /*add 1 to dig we're pointing at.*/ |
p=!.d; do u=d to y; !.u=p+1 /*add 1 to dig we're pointing at.*/ |
||
| Line 812: | Line 813: | ||
end /*u*/ |
end /*u*/ |
||
return 0 /*go back & sum this combination.*/ |
return 0 /*go back & sum this combination.*/ |
||
/*──────────────────────────────────ESORT subroutine────────────────────*/ |
/*──────────────────────────────────ESORT subroutine────────────────────*/ |
||
esort: procedure expose #. @.; parse arg N; h=N |
esort: procedure expose #. @.; parse arg N; h=N |
||
| Line 823: | Line 825: | ||
end /*while h>1*/ |
end /*while h>1*/ |
||
return |
return |
||
/* |
/*──────────────────────────────────NSORT subroutine────────────────────*/ |
||
nSort: procedure expose names.; parse arg many; h=many |
nSort: procedure expose names.; parse arg many; h=many |
||
do while h>1; h=h%2 |
do while h>1; h=h%2 |
||
| Line 834: | Line 837: | ||
end /*while h>1*/ |
end /*while h>1*/ |
||
return |
return |
||
/*──────────────────────────────────S subroutine────────────────────────*/ |
/*──────────────────────────────────S subroutine────────────────────────*/ |
||
s: if arg(1)==1 then return arg(3); |
s: if arg(1)==1 then return arg(3); return word(arg(2) 's',1) /*plural*/ |
||
/* |
/*──────────────────────────────────TELLO subroutine────────────────────*/ |
||
| ⚫ | |||
| ⚫ | |||
telly: ??=??+1; nameL= /*start with a "null" name list. */ |
telly: ??=??+1; nameL= /*start with a "null" name list. */ |
||
| Line 842: | Line 850: | ||
names.gi=@.ggg /*transform from index──> a name.*/ |
names.gi=@.ggg /*transform from index──> a name.*/ |
||
end /*gi*/ /*build dup array (to be sorted).*/ |
end /*gi*/ /*build dup array (to be sorted).*/ |
||
/* |
/*names are in order of their wt.*/ |
||
/* in order of their weight.*/ |
|||
call nSort y /*sort the names alphabetically. */ |
call nSort y /*sort the names alphabetically. */ |
||
| Line 856: | Line 863: | ||
end |
end |
||
return /*go back and keep on truckin'. */ |
return /*go back and keep on truckin'. */ |
||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
tellz: do J=1 for N /*show list of names and weights.*/ |
tellz: do J=1 for N /*show list of names and weights.*/ |
||
call tello right('['j']',30) right(@.j,11) right(#.j,5) |
call tello right('['j']',30) right(@.j,11) right(#.j,5) |
||