Anonymous user
Subset sum problem: Difference between revisions
m
→{{header|REXX}}: made the compN subroutine faster. -- ~~~~
m (→{{header|REXX}}: optimized the combN subroutine a small bit. -- ~~~~) |
m (→{{header|REXX}}: made the compN subroutine faster. -- ~~~~) |
||
Line 543:
<br>This is a brute force solution.
<lang rexx>/*REXX pgm finds some non-null subsets of a weighted list whose sum=0. */
▲arg target stop . /*get arguments from command line*/
if target=='' then target=0 /*No TARGET given? Use default.*/
if
@.=0; y=0; do N=1 until zzz=''; parse var zzz
call tell right('['N']',30)
end
solutions=0
call tell; call tell 'There are' N "entries in the table."
do chunk=1 for size▼
call combN size,chunk▼
end /*chunk*/
if
call
exit
/*─────────────────────────────────────telly subroutine─────────────────*/
telly:
do
names=names
/* names=names
end /*
call
if
call
exit
end
return
/*─────────────────────────────────────combN subroutine─────────────────*/
combN: procedure expose @. #. solutions stopAt target;
do j=1; L=!.d; do d=2 for ym; L=L !.d; end /*d*/
_=!.1; s=
do k=2 for
if s==
!.y=!.y+1; if !.y==base then if .combUp(ym) then leave
end
Line 603 ⟶ 605:
.combUp: procedure expose !. y bbase; parse arg d; if d==0 then return 1
p=!.d; do u=d to y; !.u=p+1
if !.u>=bbase+u then return .combUp(u-1)
p=!.u
| |||