topic Re: Efficient ABAP Combination Code (HEAVY MATH) in Application Development and Automation Discussions

Efficient ABAP Combination Code (HEAVY MATH)

Former Member — Wed, 18 Jan 2012 14:22:43 GMT

This will need strong MATH and ABAP skills....:

Given that I have a number of containers (N) each containing a positive quantity (Q) I need to prove

that a combination of these containers can or cannot be chosen to give a requested quantity (R).

(The true life example is some number of whole containers must be expediated and some will not).

Some containers MAY have the same quantity, but this is not required.

I have code that assignes each position to a binary bit of an (N) position number and cycles through all

binary values (1, 10, 11, 100, .... etc.) adding each combination up. This works fine up to 20 containers, but then the

geometric progression starts to make it too expensive in time to do this.

Does anyone have an efficient algorythm for this?

Re: Efficient ABAP Combination Code (HEAVY MATH)

Former Member — Wed, 18 Jan 2012 14:35:08 GMT

This is more a logic question rather than an ABAP one, but you might investigate recursive techniques. They can be simler and run more quickly.

Rob

Re: Efficient ABAP Combination Code (HEAVY MATH)

Former Member — Wed, 18 Jan 2012 15:28:03 GMT

Hi,

this problem is NP-complete, similar to [Subset sum problem|http://en.wikipedia.org/wiki/Subset_sum_problem].

So first of all check once again, if You really want to write such algorithms in ABAP...

But if You want to write in ABAP...

If You check all combinations, You will reach time out quite fast

If You make some assumptions, like quantity in each container is quite small number (hundreds? thousends? ten thousends?),

then there is a chance

I would try this algorithm:

1. Sort quantities in descending order (GT_QUANS)

2. Store requested quantity GV_REQ in table GT_VALUES.

Repeat:

3. Read and remove first value from GT_QUANS to GV_QUAN.

4. Subtract GV_REQ from each value from GT_VALUES:

a) if result is > 0:

- if result is in GT_QUANS than requested quantity can be chosen

- otherwise store result in GT_TMP

5. Append whole results from GT_TMP to GT_VALUES

6. If GT_QUANS is empty, then requested quantity can not be chosen

This is an algorithm on a paper - rewrite it to ABAP, and do tests.

My example:

1. 20 16 10 8 6 3 2 check out if 37 can be chosen

2. Store 37

In loop:

for 20: store 17

for 16: store 21 1

for 10: store 27 7 11

for 8: store 29 9 13 19 2

Stop here - 2 is in GT_QUANS, requested quantity can be chosen.

Regards,

Przemysław

Re: Efficient ABAP Combination Code (HEAVY MATH)

Former Member — Wed, 18 Jan 2012 15:30:06 GMT

The problem is, there are 2^n-n-1 unique combinations, where n is the number of containers (if I'm not totally mistaken). So with 20 containers you are already at 1048555 unique combinations. There must be a better approach to get an result, without pre-calculating all possible combinations.

Re: Efficient ABAP Combination Code (HEAVY MATH)

Former Member — Wed, 18 Jan 2012 15:42:58 GMT

Thanks for all comments and wonderfully fast.

For information, there will be a heavy weight to a single quantity in the containers, but not a requirement.

I will combine the recursion suggestion with the weighting of the highest occurring quantity and will

post the resulting code.

I have never asked a question before so will review the policies and award points as appropriate.

Re: Efficient ABAP Combination Code (HEAVY MATH)

Former Member — Wed, 18 Jan 2012 20:31:34 GMT

Resultant (and working code)....

Global data fields

GTAB contains a list of container counts and quantities.
For example 10 containers of 15 each will occupy 1 record
in the table (cnt=10, qty=15). Table should not contain 0 entries.
(Loading is not covered hereu2026..)
PMATCH is the input parameter for matching quantity.

data: begin of gtab occurs 0,

cnt type i,

qty type i,

end of gtab.

data: gstart type i, "Total container quantities before current level.

glevel type i, "Level to Process

glast type i, "Last Level to Process (Total Records in Table....)

gmatch type i, "Quantity to Match.

gdone(1). "Did we get a match?

start-of-selection.

=== Sort by occurrances (most to bottom)

sort gtab by cnt qty.

=== Set up for first level.

gstart = 0.

glevel = 1.

describe table gtab lines glast.

gmatch = pmatch.

clear gdone.

perform process_level.

&----

*& Form process_level

&----

Recursive call to see if a match can be made for combined quantity

----

FORM process_level .

data: lstart type i, "Previous total (not counting this level)

llevel type i. "This level.

data: lcnt type i, "Number of counted containers (this level)

lwrk type i.

data: ltab like gtab. "Local level

Get Local (Level) Values

lstart = gstart.

llevel = glevel.

read table gtab into ltab index llevel.

write: / 'Processing level:', llevel.

Start with NO containers at this level. (prefer to lowest level first)

clear lcnt.

do.

lwrk = lstart + ( lcnt * ltab-qty ).

--- See if calculation at this level is a match...

if lwrk = gmatch.

gdone = 'X'.

write: / 'Match!'.

exit.

endif.

--- Recurse to lower levels if needed.

if llevel < glast.

gstart = lwrk. "Starting quantity for levels to here.

glevel = llevel + 1. "Next level.

perform process_level. "GO!

if gdone = 'X'. "Did lower level produce a match?

exit.

endif.

--- Next container at this level (if present)

lcnt = lcnt + 1.

if lcnt > ltab-cnt.

exit.

endif.

enddo.

ENDFORM. " process_level