Anonymous user
Subset sum problem: Difference between revisions
m
→{{header|REXX}}: added whitespace, order subroutines in alphabetic order, added comments, changed comments, deleted superfluous semicolons. -- ~~~~
(→{{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:
end /*chunk*/
if ??==0 then ??='no' /*
call tello 'Found' ?? "subset"s(??) 'whose summed weight's(??) "=" target
exit /*stick a fork in it, we done.*/
/*
combN: procedure expose @. #. ?? stopAt target; parse arg x,y; !.=0
base=x+1; bbase=base-y; ym=y-1 /*!.n are the combination digits*/
do n=1 for y; !.n=n;
do j=1; _=!.1; s=#._ /*get 1st dig & the sum*/
if s>target then leave /*1st dig>target? Then we're done*/
do k=2 for ym; _=!.k; s=s+#._
if s>target then do; if .combUp(k-1) then return; iterate j; end
end
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*/
end
return /*done with this combination set.*/
.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.*/
Line 812 ⟶ 813:
end /*u*/
return 0 /*go back & sum this combination.*/
/*──────────────────────────────────ESORT subroutine────────────────────*/
esort: procedure expose #. @.; parse arg N; h=N
Line 823 ⟶ 825:
end /*while h>1*/
return
/*
nSort: procedure expose names.; parse arg many; h=many
do while h>1; h=h%2
Line 834 ⟶ 837:
end /*while h>1*/
return
/*──────────────────────────────────S subroutine────────────────────────*/
s: if arg(1)==1 then return arg(3);
/*
/*
telly: ??=??+1; nameL= /*start with a "null" name list. */
Line 842 ⟶ 850:
names.gi=@.ggg /*transform from index──> a name.*/
end /*gi*/ /*build dup array (to be sorted).*/
/*
call nSort y /*sort the names alphabetically. */
Line 856 ⟶ 863:
end
return /*go back and keep on truckin'. */
▲/*──────────────────────────────────tello subroutine────────────────────*/
/*
▲tello: say arg(1); call lineout 'SUBSET.'y,arg(1) /*write to file*/; return
▲/*──────────────────────────────────tellz subroutine────────────────────*/
tellz: do J=1 for N /*show list of names and weights.*/
call tello right('['j']',30) right(@.j,11) right(#.j,5)
| |||