Skip to Content

Subset Sum Problem Statement

An instance of the Subset Sum problem is a pair (S, t), where S = {x1, x2,…, xn} is a set ofPositive integers and t (the target) is a positive integer. The decision problem asks for a subset of S whose sum is as large as possible, but not larger than t.

Real Time Example

For handling unit, suppose a delivery having 35 line items and each item having quantity associated with it, and we want to pack these items in a pallet, there may be multiple rules to accommodate item quantity into pallet like;

  • Item quantity can’t be divided to fill in pallet.
  • Any number of item can mix in a pallet but it should return optimum packing
  • Each pallet having its target maximum quantity, which describe how much quantity it can hold, so ultimate aim is to make a combination for above mentioned 35 items which fit nearest to the pallet capacity.
  • Based on the combination of items and pallet capacity, some priority has been decided on which if exact combination of items match with pallet capacity then it is highest priority match and need to take this combination in solution, and later on other priority has been changed as per the requirement. 

Challenges

Earlier we implemented brute force algorithm to find different combination of items for implement this there is need to create all possible combination of items into internal table and then access this table to retrieve possible optimum solution, this solution is worked for 20 items if any delivery having more than 20 items then performance problem occurs and program giving dump saying system no roll.

sustem no roll.png

Reason for this dump is, if program is trying to build combination of 35 line items then number of combination grown exponentially, total combination can be derived by (2n ) where n is the number of items, below table will give an idea for combination will increased for larger the number of items.

/wp-content/uploads/2012/10/combination_143568.png

Hence this solution is not good for packing of more than 20 line items.

Dynamic Programming approach to solve subset sum problem

INPUT: A collection of item S ( 0, . . . , n)  of positive integers, and a positive integer weight S1(0,….W).

OUTPUT: A subset of the S that sum to W

Algorithm:

ss(n,W)

array M(n,W)

array<[0….n, 0….w]

for (i=1,2…n)

  for (w= 0,1…W)

    if w<wi.

       m[i,w] = M[i-1,w]

     else.

       m[i,w] = max{m[i-1,w, wi + m[i-1,w-wi]

}

I found a very good presentation in yotube on following link to understand brute force and subset sum dynamic programming algorithm, and these references are very helpful to develop ABAP solution for subset sum problem.

http://www.youtube.com/watch?v=r1zz5OyB3K0&list=PL6B1D18AEC44956AF&index=1&feature=plpp_video

Demo program in ABAP for subset sum problem using Dynamic Programming:

*&———————————————————————*
*& Report  YG03
*&
*&———————————————————————*
*&
*&
*&———————————————————————*
{CODE}REPORT  yg03.

PARAMETERS p_weight type i OBLIGATORY DEFAULT 270.
parameters p_lines type i DEFAULT 31.

DATA: BEGIN OF gtab OCCURS 0,
               cnt TYPE i,
               qty
TYPE i,
           END OF gtab.
DATA wt_str(5) TYPE c.
DATA : lo_element  TYPE REF TO cl_abap_elemdescr,
            lo_new_type
TYPE REF TO cl_abap_structdescr,
            lo_new_tab 
TYPE REF TO cl_abap_tabledescr,
            lt_comp    
TYPE cl_abap_structdescr=>component_table,

            lo_data     TYPE REF TO data,
            lo_data1   
TYPE REF TO data,
            lo_data_s  
TYPE REF TO data,
            lo_data_s1 
TYPE REF TO data,
            la_comp    
LIKE LINE OF lt_comp.

FIELDSYMBOLS: <f_tab>   TYPE STANDARD TABLE,
               <a_tab>  
TYPE STANDARD TABLE,
               <f_line> 
TYPE ANY,
               <f_line1> 
TYPE ANY,
               <f_line2> 
TYPE ANY,
               <f_field>
TYPE i,
               <f_field1>
TYPE i,
               <f_fieldn>
TYPE i.

DATA : BEGIN OF field OCCURS 0,
                 
index TYPE i,
                  name
(30) TYPE c,
                 
value TYPE i,
         
END OF field.

DATA ln TYPE i.
DATA weight TYPE i.
* variable for revert back logic******
DATA ln_row TYPE i.
DATA ln_col TYPE i.
DATA temp_idx TYPE i.
DATA temp1_idx type i.
DATA temp2_idx type i.
data temp_val type i.

FIELD-SYMBOLS : <f_1> TYPE ANY,
                               <f_2>
TYPE ANY.
DATA : BEGIN OF final_item OCCURS 0,
                  item
TYPE i,
           
END OF final_item.
data total type i.
ln
= p_lines.
**create item internal table to create diffrent combination

DO ln TIMES.
   CASE syindex.
   
WHEN 1.
       gtab
cnt = syindex * .
       gtab
qty = 100.
      
APPEND gtab.
   
WHEN 2.
      gtab
cnt = syindex * .
      gtab
qty = 54.
     
APPEND gtab.

   WHEN 3.
      gtab
cnt = syindex * .
      gtab
qty 51.
     
APPEND gtab.
   
WHEN 4.
      gtab
cnt = syindex * .
      gtab
qty 65.
     
APPEND gtab.
   
WHEN 5.
      gtab
cnt = syindex * .
      gtab
qty 57.
     
APPEND gtab.
   
WHEN 6.
      gtab
cnt = syindex * .
      gtab
qty 57.
     
APPEND gtab.
   
WHEN 7.
      gtab
cnt = syindex * .
      gtab
qty 57.
     
APPEND gtab.
  
WHEN 13.
      gtab
cnt = syindex * .
      gtab
qty 270.
     
APPEND gtab.
   
WHEN OTHERS.
      gtab
cnt = syindex * .
      gtab
qty 1.
     
APPEND gtab.
 
ENDCASE.
ENDDO.
*sort gtab by qty ASCENDING.
weight = p_weight.
wt_str
= ‘0’.
CONCATENATE ‘WT_’ wt_str INTO la_compname.
CONDENSE la_compname NOGAPS.
la_comp
type = cl_abap_elemdescr=>get_i( ).
APPEND la_comp TO  lt_comp.
fieldindex = 1.
fieldvalue = 0.
fieldname = la_compname.
APPEND field.
CLEAR field.
CLEAR: la_comp.
** Dynamic Column Generation
DO weight TIMES.

  CLEAR wt_str.
  wt_str
= syindex.
 
CONCATENATE ‘WT_’ wt_str INTO la_compname.
 
CONDENSE la_compname NOGAPS.
 
fieldindex = 1 + syindex.
 
fieldvalue = syindex.
 
fieldname = la_compname.
 
APPEND field.
  la_comp
type = cl_abap_elemdescr=>get_i( ).
 
APPEND la_comp TO  lt_comp.
 
CLEAR: la_comp.
ENDDO.
lo_new_type
= cl_abap_structdescr=>create( lt_comp ).
* 4. New Table type
lo_new_tab
= cl_abap_tabledescr=>create(
                p_line_type 
= lo_new_type
                p_table_kind
= cl_abap_tabledescr=>tablekind_std
                p_unique    
= abap_false ).
CREATE DATA lo_data TYPE HANDLE lo_new_tab.
CREATE DATA lo_data_s TYPE HANDLE lo_new_type.
ASSIGN lo_data->* TO <f_tab>.     “main table
ASSIGN lo_data_s->* TO <f_line1>.
DO.
 
ASSIGN COMPONENT syindex OF STRUCTURE <f_line1> TO <f_field>.
 
IF sysubrc IS INITIAL.
    <f_field>
= 0.
 
ELSE.
   
EXIT.
 
ENDIF.
ENDDO.
** creating  first row in dynamic table with zeros
INSERT <f_line1> INTO TABLE <f_tab>.
UNASSIGN
: <f_field>, <f_line1>.
DATA : row_index TYPE i,
       col_index
TYPE i,
       call_row_index
TYPE i,
       call_col_index
TYPE i,
       call_row_index1
TYPE i,
       call_col_index1
TYPE i,
       call_row_index2
TYPE i,
       call_col_index2
TYPE i,
       temp1
TYPE i,
       temp2
TYPE i,
       temp
TYPE i,
       temp3
TYPE i,
       flag_optimal
TYPE i,
       wa
LIKE LINE OF field.
clear : row_index,
        col_index
,
        call_row_index
,
        call_col_index
.
**creating record in dynamic table for
* possible combination of item
DO ln TIMES.
  row_index
= syindex + 1.    “{i}
 
READ TABLE gtab INDEX syindex.
 
LOOP AT field.
   
CLEAR flag_optimal.
    col_index
= sytabix.
   
IF fieldvalue < gtabqty.
      call_row_index
= row_index 1.
      call_col_index
= col_index.
     
READ TABLE <f_tab> ASSIGNING <f_line1> INDEX call_row_index.
     
ASSIGN COMPONENT fieldname OF STRUCTURE <f_line1> TO <f_field>.
      temp
= <f_field> .
   
ELSE.
      call_row_index1
= row_index 1.
      call_col_index1
= col_index.
     
READ TABLE <f_tab> ASSIGNING <f_line1> INDEX call_row_index1.
     
ASSIGN COMPONENT fieldname OF STRUCTURE <f_line1> TO <f_field>.
      temp1
= <f_field> .

      call_row_index2 = row_index 1.
      temp3
= fieldvalue gtabqty.
     
READ TABLE field INTO wa WITH KEY value = temp3.
     
IF sysubrc IS INITIAL.
        call_col_index2
= waindex.
     
ENDIF.
     
READ TABLE <f_tab> ASSIGNING <f_line1> INDEX call_row_index2.
     
ASSIGN COMPONENT call_col_index2 OF STRUCTURE <f_line1> TO <f_field1>.
      temp2
= <f_field1> + gtabqty.
     
IF temp2 > temp1.
        temp
= temp2.
     
ELSE.
        temp
= temp1.
     
ENDIF.
   
ENDIF.
   
READ TABLE <f_tab> ASSIGNING <f_line1> INDEX row_index.
   
IF sysubrc IS INITIAL.
     
ASSIGN COMPONENT col_index OF STRUCTURE <f_line1> TO <f_fieldn>.
      <f_fieldn>
= temp.
   
ELSE.
     
ASSIGN COMPONENT col_index OF STRUCTURE <f_line1> TO <f_fieldn>.
      <f_fieldn>
= temp.
     
INSERT <f_line1> INTO TABLE <f_tab>.
   
ENDIF.
   
CLEAR field.
 
ENDLOOP.
ENDDO.
*************traceback exact items from dynamic table********************
DESCRIBE TABLE <f_tab> LINES ln_row.
DESCRIBE TABLE field LINES ln_col.
row_index
= ln_row.
DO ln_row TIMES.
emp2_idx
row_index.
DO row_index TIMES.
   temp_idx
= temp2_idx 1.
   
READ TABLE <f_tab> ASSIGNING <f_line1> INDEX temp2_idx.

   ASSIGN COMPONENT ln_col OF STRUCTURE <f_line1> TO <f_1>.
   
READ TABLE <f_tab> ASSIGNING <f_line1> INDEX temp_idx.
   
ASSIGN COMPONENT ln_col OF STRUCTURE <f_line1> TO <f_2>.

    IF <f_1> NE <f_2>.
      temp1_idx
= temp2_idx.
     
EXIT.
   
ENDIF.
    temp2_idx
= temp2_idx 1.
 
ENDDO.
row_index
= temp1_idx.
temp1_idx
= temp1_idx 1.

read table gtab index temp1_idx.
 
if sysubrc is INITIAL.
    final_item
item = gtabcnt.
   
append final_item.
   
read table field with key index = ln_col.
   
if sysubrc is INITIAL.
     temp_val
= fieldvalue gtabqty.
   
endif.
  
read table field with key value = temp_val.
    ln_col
= fieldindex.
 
endif.
  row_index
= row_index 1.
if row_index = 0.
 
exit.
endif.
if ln_col = 1.
 
exit.
endif.
clear temp1_idx.
ENDDO.
loop at final_item.
 
at first.
   
write : / ‘       Item’, ‘         Quantity’.
 
endat.
read table gtab with key cnt = final_itemitem.
if sysubrc is INITIAL.
 
write : / gtabcnt,gtabqty.
  total
= total + gtabqty.
endif.
at last.
  
write : / ‘______________________________’.
  
write : / ‘Total of Qty =’, total.
endat.
endloop.{/CODE}

_________________________________________________________________________________________

Selection Screen for above program:

selection screen.png

  1. Optimum pallet weight is the target weight for which combination of item we want to search.
  2. Number of lines is the total number of item in delivery; in demo program I have filled this data in internal table (gtab) using random quantity.

Output of above program for 270 and 300 target quantity:

/wp-content/uploads/2012/10/output_143573.png

Out of 31 items, combination of set s(1,2,3,4) is giving the target pallet weight so this 1 solution then on next run delete above 4 items from gtab and again execute this logic to find second set of optimum solution and so on.

Execution of this program is very fast, to find first optimum solution of 35 line items it took around 2 seconds.

Post your comment in this blog if you find it helpful.

Thanks and Regards,

Gagan Choudha

To report this post you need to login first.

Be the first to leave a comment

You must be Logged on to comment or reply to a post.

Leave a Reply