What is this knapsack? The point is we use the knapsack algorithm to get optimal results.
Example Case: we have 3 items that we should bring by our cart to sell. But our cart is only can bring max 50kg, and that means the cart is not capable of bringing all the items. Which items we should bring to get the maximum profit?
item 1 : weight = 10kg ; profit = 60
item 2 : weight = 20kg ; profit = 100
item 3 : weight = 30kg ; profit = 120
we would like to search max profit with max weight = 50
expected: the result should be items 2 & 3 chosen with total weight = 50 and total profit = 220
How we get that with ABAP. Here I share my example code:
REPORT zknapsack.
TYPES: BEGIN OF ty_item,
profit TYPE i,
weight TYPE i,
END OF ty_item,
tt_item TYPE STANDARD TABLE OF ty_item WITH EMPTY KEY.
TYPES: BEGIN OF ty_sum,
sum_w TYPE i,
sum_p TYPE i,
items TYPE tt_item,
END OF ty_sum.
CLASS lcl_knapsack DEFINITION.
PUBLIC SECTION.
CLASS-METHODS:
get_optimal
IMPORTING
im_w_max TYPE i
imt_item TYPE tt_item
im_n TYPE i
RETURNING VALUE(rs_sum) TYPE ty_sum.
PRIVATE SECTION.
CLASS-METHODS: get_max
IMPORTING
im_data1 TYPE ty_sum
im_data2 TYPE ty_sum
RETURNING VALUE(rs_sum) TYPE ty_sum.
ENDCLASS.
CLASS lcl_knapsack IMPLEMENTATION.
METHOD get_optimal.
IF im_n = 0 OR im_w_max <= 0.
RETURN.
ENDIF.
IF imt_item[ im_n ]-weight > im_w_max.
rs_sum = get_optimal( im_w_max = im_w_max imt_item = imt_item im_n = im_n - 1 ).
ELSE.
DATA(l_data) = get_optimal( im_w_max = im_w_max - imt_item[ im_n ]-weight
imt_item = imt_item
im_n = im_n - 1 ).
l_data-sum_w = l_data-sum_w + imt_item[ im_n ]-weight.
l_data-sum_p = l_data-sum_p + imt_item[ im_n ]-profit.
APPEND imt_item[ im_n ] TO l_data-items.
rs_sum = get_max( im_data1 = l_data
im_data2 = get_optimal( im_w_max = im_w_max imt_item = imt_item im_n = im_n - 1 ) ).
ENDIF.
ENDMETHOD. " get_optimal
METHOD get_max.
IF im_data1-sum_p < im_data2-sum_p.
rs_sum = im_data2.
ELSE.
rs_sum = im_data1.
ENDIF.
ENDMETHOD. " get_max
ENDCLASS.
START-OF-SELECTION.
* ------------------------------------------------------------------------------------------
" CASE:
" item 1 : weight = 10 ; profit = 60
" item 2 : weight = 20 ; profit = 100
" item 3 : weight = 30 ; profit = 120
" we would like to search max profit with max weight = 50
" the result should be items 2 & 3 chosen with total weight = 50 and total profit = 220
* ------------------------------------------------------------------------------------------
DATA:
lt_item TYPE tt_item,
lv_n TYPE i,
lv_w_max TYPE i.
lt_item = VALUE #( ( weight = 10 profit = 60 )
( weight = 20 profit = 100 )
( weight = 30 profit = 120 ) ).
lv_n = lines( lt_item ).
lv_w_max = 50.
DATA(ls_result) = lcl_knapsack=>get_optimal(
EXPORTING
im_w_max = lv_w_max
imt_item = lt_item
im_n = lv_n
).
WRITE:/ ls_result-sum_p, ls_result-sum_w.Don’t only copy and paste on your code but please understand the concept. I hope you can do this better. Thank you.:)
references: