Anonymous user
Subset sum problem: Difference between revisions
→version 2: optimized the previous version, it's faster by a facter of four or so. -- ~~~~
(→version 1: optimized part of the combN subroutine for faster execution. -- ~~~~) |
(→version 2: optimized the previous version, it's faster by a facter of four or so. -- ~~~~) |
||
Line 813:
===version 2===
This version requires the data to be in ascending order (by weight).
<br>Code could've been included to sort the table, but the extra code would've made the
program more bulkier, so the list was just sorted externally.
<br>It's
<lang rexx>/*REXX pgm finds some non-null subsets of a weighted list whose sum = 0.
arg target stopAt . /*get arguments from command line*/
if target=='' then target=0 /*No TARGET given? Use default.*/
Line 855:
@.=0; y=0; do N=1 until zzz=''; parse var zzz @.N #.N zzz
call
end /*N*/
solutions=0
call
do chunk=1 for N
call combN N,chunk
end /*chunk*/
if solutions==0 then solutions='no'
call
exit
/*─────────────────────────────────────telly subroutine─────────────────*/
Line 875:
end /*g*/
call
if solutions>=stopAt &,
stopAt\==0 then do
call
exit
end
return
/*─────────────────────────────────────combN subroutine─────────────────*/
combN: procedure expose @. #. solutions 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;
do j=1
_=!.1; s=#._; if s>target then leave
do k=2 for ym until s>target; _=!.k; s=s+#._; end /*sum weights.*/▼
if s==target then call telly▼
!.y=!.y+1; if !.y==base then if .combUp(ym) then leave▼
if s>target then do; if .combUp(k-1) then return; iterate j; end
end /*k*/
▲ 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 /*j*/
return
| |||