Looking for a special algorithm in ABAP...

[Former Member]

Hi there,

I have to implement an algorithm that seems to be very complex and I am looking for ideas and hints which could help me to create a method that has also a good performance.

The following I have to create:

I get an internal table which includes two columns, the first is somtehing like a key which is distinct. The other field in the table is a value from type P.

The other thing I get is a single value also as packed value.

Now my task is to check if the single value can be calculated by addition of some entries of the table. In other words: Is is possible to exactly get the given value by addition of N rows in the internal table (every row can only be used one time). Anf if is possible, I want to give back the list of keys which have to be used for getting the result.

For example:

Table:

4711 - 100.00
4712 - 200.00
4713 - 300.00
4714 - 500.00

Given value: 700

Returning list:

4712
4714

Has someone a idea how to implement such a function in SAP?

Thank you!

Kind regards

Jens

[Former Member]

Hi there,

I have to implement an algorithm that seems to be very complex and I am looking for ideas and hints which could help me to create a method that has also a good performance.

The following I have to create:

I get an internal table which includes two columns, the first is somtehing like a key which is distinct. The other field in the table is a value from type P.

The other thing I get is a single value also as packed value.

Now my task is to check if the single value can be calculated by addition of some entries of the table. In other words: Is is possible to exactly get the given value by addition of N rows in the internal table (every row can only be used one time). Anf if is possible, I want to give back the list of keys which have to be used for getting the result.

For example:

Table:

4711 - 100.00
4712 - 200.00
4713 - 300.00
4714 - 500.00

Given value: 700

Returning list:

4712
4714

Has someone a idea how to implement such a function in SAP?

Thank you!

Kind regards

Jens

[_IvanFemia_]

Hi,

You want a solution or all the possible solution?

maybe the back-tracking algorithm, you can also sort the table descending on the second field.

In other words,

1 - Loop on the table.

2 - Calculate the partial sum

3 - Check the difference to the goal

4 - Start looping on the table starting from the first value lower or equal to the difference calculated on point 3.

Regards,

Ivan

[Former Member]

No complete solution is needed, only some approaches

Thank you

[Former Member]

So your internal table contains these 4 values only or you just providing an example of values.

[Former Member]

These 4 entries are only examples. The table can include only two or perhaps 100 entries, so the coding has to be flexible because the number of entries is known only at runtime.

[Former Member]

Here's a test report I wrote, there are some inefficiencies in it but you can add some conditions and improve the performance . Cheers.

REPORT  ztest.

TYPES: BEGIN OF ty_itab,
  key   TYPE num6,
  value TYPE p,
END OF ty_itab.

DATA: lt_itab     TYPE TABLE OF ty_itab,
      ls_itab     TYPE          ty_itab,
      lt_results  TYPE TABLE OF ty_itab.

DATA: lv_index     TYPE sy-tabix,
      lv_total    TYPE p,
      lv_part_tot TYPE p,
      lv_required_value TYPE p.

DATA: lv_lines    TYPE    sy-tabix.
FIELD-SYMBOLS:
      <itab>      LIKE LINE OF lt_itab.

SELECTION-SCREEN BEGIN OF BLOCK b1.
PARAMETERS: p_req LIKE lv_required_value.

SELECTION-SCREEN END OF BLOCK b1.



* load some data for testing.

DO 10 TIMES.
  ls_itab-key = sy-index.
  ls_itab-value = sy-index * 100.
  APPEND ls_itab TO lt_itab.


ENDDO.
lv_required_value = p_req.
DELETE lt_itab WHERE value > lv_required_value.
DESCRIBE TABLE lt_itab LINES lv_lines.
BREAK-POINT.
DO lv_lines TIMES.
  lv_index = sy-index.

  CLEAR: lv_total, lt_results[].

  READ TABLE lt_itab ASSIGNING <itab> INDEX lv_index.
  CHECK sy-subrc IS INITIAL.
  lv_total = <itab>-value.

  lv_part_tot = lv_required_value - lv_total.
  LOOP AT lt_itab ASSIGNING <itab> FROM LV_INDEX WHERE value <= lv_part_tot.
    IF sy-tabix  = lv_index.
      APPEND <itab> TO lt_results[].
      CONTINUE.
    ENDIF.

    lv_total    = lv_total + <itab>-value.
    lv_part_tot = lv_required_value  - lv_total.
    APPEND <itab> TO lt_results.
    IF lv_part_tot  <= 0.
      EXIT.
    ENDIF.
  ENDLOOP.
  IF lv_part_tot = 0.
    EXIT.
  ENDIF.

ENDDO.

LOOP AT lt_results ASSIGNING <itab>.
  WRITE : /, '|', <itab>-key, <itab>-value, '|'.
ENDLOOP.

Edited by: tyler durden on Apr 4, 2009 10:30 PM

[Former Member]

Thank you very much for your coding.

I tested it but it doesn't work in all cases. I added some other numbers to the internal table manually, see the following coding:

REPORT  ztest.

TYPES: BEGIN OF ty_itab,
  key   TYPE num6,
  value TYPE p,
END OF ty_itab.

DATA: lt_itab     TYPE TABLE OF ty_itab,
      ls_itab     TYPE          ty_itab,
      lt_results  TYPE TABLE OF ty_itab.

DATA: lv_index     TYPE sy-tabix,
      lv_total    TYPE p,
      lv_part_tot TYPE p,
      lv_required_value TYPE p.

DATA: lv_lines    TYPE    sy-tabix.
FIELD-SYMBOLS:
      <itab>      LIKE LINE OF lt_itab.

SELECTION-SCREEN BEGIN OF BLOCK b1.
PARAMETERS: p_req LIKE lv_required_value.

SELECTION-SCREEN END OF BLOCK b1.



* load some data for testing.

*DO 10 TIMES.
*  ls_itab-key = sy-index.
*  ls_itab-value = sy-index * 100.
*  APPEND ls_itab TO lt_itab.
*ENDDO.

  ls_itab-key = 1.
  ls_itab-value = 50.
  APPEND ls_itab TO lt_itab.

  ls_itab-key = 2.
  ls_itab-value = 100.
  APPEND ls_itab TO lt_itab.

  ls_itab-key = 3.
  ls_itab-value = 25.
  APPEND ls_itab TO lt_itab.

  ls_itab-key = 4.
  ls_itab-value = 99.
  APPEND ls_itab TO lt_itab.

  ls_itab-key = 5.
  ls_itab-value = 11.
  APPEND ls_itab TO lt_itab.

SORT lt_itab BY value ASCENDING.

lv_required_value = p_req.
DELETE lt_itab WHERE value > lv_required_value.
DESCRIBE TABLE lt_itab LINES lv_lines.
BREAK-POINT.
DO lv_lines TIMES.
  lv_index = sy-index.

  CLEAR: lv_total, lt_results[].

  READ TABLE lt_itab ASSIGNING <itab> INDEX lv_index.
  CHECK sy-subrc IS INITIAL.
  lv_total = <itab>-value.

  lv_part_tot = lv_required_value - lv_total.
  LOOP AT lt_itab ASSIGNING <itab> FROM LV_INDEX WHERE value <= lv_part_tot.
    IF sy-tabix  = lv_index.
      APPEND <itab> TO lt_results[].
      CONTINUE.
    ENDIF.

    lv_total    = lv_total + <itab>-value.
    lv_part_tot = lv_required_value  - lv_total.
    APPEND <itab> TO lt_results.
    IF lv_part_tot  <= 0.
      EXIT.
    ENDIF.
  ENDLOOP.
  IF lv_part_tot = 0.
    EXIT.
  ENDIF.

ENDDO.

LOOP AT lt_results ASSIGNING <itab>.
  WRITE : /, '|', <itab>-key, <itab>-value, '|'.
ENDLOOP.

For example for required value 110 (Key 4 + 5) or 161 (Key 1 + 2 + 5) I get no result.

Kind regards

Jens

[Former Member]

i had started for two values and this is my logic for ur query . after looking into ur last thread i m trying to refine this for more than two values .

 parameters: p_price type i obligatory.

types: Begin of str_tbl,
     VAL(4) TYPE C,
     PRICE TYPE I,
     End of str_tbl.

data: It_tbl type standard table of str_tbl,
      wa_tbl like line of it_tbl,
      it_cln type  standard table of str_tbl,
      wa_cln type str_tbl.


clear wa_tbl.
wa_tbl-val = '4711'.
wa_tbl-price = 100.
append wa_tbl to it_tbl.

clear wa_tbl.
wa_tbl-val = '4712'.
wa_tbl-price = 200.
append wa_tbl to it_tbl.

clear wa_tbl.
wa_tbl-val = '4713'.
wa_tbl-price = 300.
append wa_tbl to it_tbl.

clear wa_tbl.
wa_tbl-val = '4720'.
wa_tbl-price = 500.
append wa_tbl to it_tbl.

sort it_tbl by val.
it_cln[] = it_tbl[].

data : lv_dif type i.


*algorithm needs to check what is the key value provided and start
*comparing the values as what will fit in to the current iteration.

loop at it_tbl into wa_tbl.
     lv_dif =   p_price - wa_tbl-price   .
     if lv_dif > 0.
     read table it_cln into wa_cln with key price = lv_dif binary search.
     if sy-subrc eq 0 .

      write: / 'Result is from' ,wa_tbl-val , wa_tbl-price , 'and' ,wa_cln-val ,                
                wa_cln-price.
      exit.
     endif.
    endif.
endloop.
  

let me check if i can improvise this still .

br,

vijay.

[Former Member]

chk this and it can be refined further ..execute the code for ur variations .

  
REPORT  ZEX19.

parameters: p_price type i obligatory.

types: Begin of str_tbl,
       VAL(4) TYPE C,
       PRICE TYPE I,
       End of str_tbl.

data: It_tbl type standard table of str_tbl,
      wa_tbl like line of it_tbl,
*      it_cln type  standard table of str_tbl,
*      wa_cln type str_tbl,
      it_cln2 type  standard table of str_tbl,
      wa_cln2 type str_tbl.
data : p_priorg type i,
       lv_cnt type i.


clear wa_tbl.
wa_tbl-val = '1'.
wa_tbl-price = 50.
append wa_tbl to it_tbl.

clear wa_tbl.
wa_tbl-val = '2'.
wa_tbl-price = 100.
append wa_tbl to it_tbl.

clear wa_tbl.
wa_tbl-val = '3'.
wa_tbl-price = 25.
append wa_tbl to it_tbl.

clear wa_tbl.
wa_tbl-val = '4'.
wa_tbl-price = 99.
append wa_tbl to it_tbl.

clear wa_tbl.
wa_tbl-val = '5'.
wa_tbl-price = 11.
append wa_tbl to it_tbl.


sort it_tbl by val.
*it_cln[] = it_tbl[].

data : lv_dif type i,
       lv_nil type c.

loop at it_tbl into wa_tbl.
  write:/ wa_tbl-val , wa_tbl-price.
endloop.
skip 2. write :/ sy-uline(75).
*algorithm needs to check what is the key value provided and start
*comparing the values as what will fit in to the current iteration."app for 2 vals
*-->more than 2 vals
*need to check particle split and cumulate it to the key for stat iteration
*0+1+2....n.(n+1)
*consider  : sort on 2nd field .
*161 = 50 + 100 + 11 --> 1, 2, 5 "<--ex

sort it_tbl by price descending."chk this
delete it_tbl where price gt p_price."limit only valid entries.
perform chk_val.

perform disp_out.

*&---------------------------------------------------------------------*
*&      Form  CHK_VAL
*&---------------------------------------------------------------------*
*       text
*----------------------------------------------------------------------*
*  -->  p1        text
*  <--  p2        text
*----------------------------------------------------------------------*
FORM CHK_VAL .
p_priorg = p_price.

loop at it_tbl into wa_tbl.
  lv_dif = p_price - wa_tbl-price.
  if lv_dif >= 0. "mark as consider.
    p_price = lv_dif.

    wa_cln2-val = wa_tbl-val.
    wa_cln2-price = wa_tbl-price.
    append wa_cln2 to it_cln2.
    if  lv_dif eq 0. "equated
      exit.
    endif.
  endif.
  at last .
    if lv_dif ne 0.
      refresh it_cln2[].
      clear wa_cln2.
 *    lv_nil  = 'X'.
      describe table it_tbl lines lv_cnt.
      if lv_cnt > 1.
      delete it_tbl index 1. "can be replaced with a clone
      p_price = p_priorg.
      perform chk_val. "reset the operation
      endif.
*     else.
*      perform disp_out.
    endif.
  endat.
endloop.

ENDFORM.                    " CHK_VAL
*&---------------------------------------------------------------------*
*&      Form  DISP_OUT
*&---------------------------------------------------------------------*
*       text
*----------------------------------------------------------------------*
*  -->  p1        text
*  <--  p2        text
*----------------------------------------------------------------------*
FORM DISP_OUT .
if it_cln2[] is not initial.
loop at it_cln2 into wa_cln2.
  write:/ wa_cln2-val , wa_cln2-price left-justified.
endloop.
else.
write:/ 'no hit for the key value', p_priorg .

endif.
ENDFORM.                    " DISP_OUT

let me know ur feedback .

br,

vijay.