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.
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.
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.
FIELD-SYMBOLS: <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 sy-index.
WHEN 1.
gtab-cnt = sy-index * 1 .
gtab-qty = 100.
APPEND gtab.
WHEN 2.
gtab-cnt = sy-index * 1 .
gtab-qty = 54.
APPEND gtab.
WHEN 3.
gtab-cnt = sy-index * 1 .
gtab-qty = 51.
APPEND gtab.
WHEN 4.
gtab-cnt = sy-index * 1 .
gtab-qty = 65.
APPEND gtab.
WHEN 5.
gtab-cnt = sy-index * 1 .
gtab-qty = 57.
APPEND gtab.
WHEN 6.
gtab-cnt = sy-index * 1 .
gtab-qty = 57.
APPEND gtab.
WHEN 7.
gtab-cnt = sy-index * 1 .
gtab-qty = 57.
APPEND gtab.
WHEN 13.
gtab-cnt = sy-index * 1 .
gtab-qty = 270.
APPEND gtab.
WHEN OTHERS.
gtab-cnt = sy-index * 1 .
gtab-qty = 1.
APPEND gtab.
ENDCASE.
ENDDO.
*sort gtab by qty ASCENDING.
weight = p_weight.
wt_str = '0'.
CONCATENATE 'WT_' wt_str INTO la_comp-name.
CONDENSE la_comp-name NO-GAPS.
la_comp-type = cl_abap_elemdescr=>get_i( ).
APPEND la_comp TO lt_comp.
field-index = 1.
field-value = 0.
field-name = la_comp-name.
APPEND field.
CLEAR field.
CLEAR: la_comp.
** Dynamic Column Generation
DO weight TIMES.
CLEAR wt_str.
wt_str = sy-index.
CONCATENATE 'WT_' wt_str INTO la_comp-name.
CONDENSE la_comp-name NO-GAPS.
field-index = 1 + sy-index.
field-value = sy-index.
field-name = la_comp-name.
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 sy-index OF STRUCTURE <f_line1> TO <f_field>.
IF sy-subrc 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 = sy-index + 1. "{i}
READ TABLE gtab INDEX sy-index.
LOOP AT field.
CLEAR flag_optimal.
col_index = sy-tabix.
IF field-value < gtab-qty.
call_row_index = row_index - 1.
call_col_index = col_index.
READ TABLE <f_tab> ASSIGNING <f_line1> INDEX call_row_index.
ASSIGN COMPONENT field-name 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 field-name OF STRUCTURE <f_line1> TO <f_field>.
temp1 = <f_field> .
call_row_index2 = row_index - 1.
temp3 = field-value - gtab-qty.
READ TABLE field INTO wa WITH KEY value = temp3.
IF sy-subrc IS INITIAL.
call_col_index2 = wa-index.
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> + gtab-qty.
IF temp2 > temp1.
temp = temp2.
ELSE.
temp = temp1.
ENDIF.
ENDIF.
READ TABLE <f_tab> ASSIGNING <f_line1> INDEX row_index.
IF sy-subrc 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 sy-subrc is INITIAL.
final_item-item = gtab-cnt.
append final_item.
read table field with key index = ln_col.
if sy-subrc is INITIAL.
temp_val = field-value - gtab-qty.
endif.
read table field with key value = temp_val.
ln_col = field-index.
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_item-item.
if sy-subrc is INITIAL.
write : / gtab-cnt,gtab-qty.
total = total + gtab-qty.
endif.
at last.
write : / '______________________________'.
write : / 'Total of Qty =', total.
endat.
endloop.{/CODE}
_________________________________________________________________________________________
Selection Screen for above program:
- Optimum pallet weight is the target weight for which combination of item we want to search.
- 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:
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
- SAP Managed Tags:
