Ein Knapsack-Problem

*&---------------------------------------------------------------------*
*& Report ZZ_OPT_KNAPSACK
*&---------------------------------------------------------------------*
*& Versucht, eine Teilmenge des Multi-Sets PARTS so zu addieren,
*& daß die Summe möglichst nahe an p_result herankommt, sie aber nicht
*& übersteigt
*&---------------------------------------------------------------------*
report zz_opt_knapsack_rpl.

parameters:
  p_result type i default 50,
  p_parts  type string default `25, 20, 15, 10, 5, 2`.


class lcl_opt definition.
  public section.

* Behälter für eine Summe und eine Zahlenmenge
    types:
      begin of ty_parts_sum,
        parts type int4_table,
        sum   type i,
      end of ty_parts_sum.

    class-methods:
      start,
      get_best
        importing is_input      type ty_parts_sum
        returning value(es_opt) type ty_parts_sum.
endclass.

class lcl_opt implementation.
  method start.

* Vorbereitung
    condense p_parts no-gaps.
    split p_parts at ',' into table data(lt_parts).

* Ausführung
    data(ls_opt) = get_best( value #(
      parts = conv #( lt_parts )
      sum   = p_result
    ) ).

* Ergebnis ausgeben
    sort ls_opt-parts descending.
    lt_parts = value #( for i in ls_opt-parts ( condense( conv string( i ) ) ) ).
    write: /
      ls_opt-sum no-gap, ':',
      concat_lines_of( table = lt_parts sep = `+` ).

  endmethod.
  method get_best.

    loop at is_input-parts into data(lv_part)
      where table_line = is_input-sum.
* Triviale Lösung gefunden
      es_opt = value #(
        sum   = is_input-sum
        parts = value #( ( lv_part ) )
      ).
      return.
    endloop.

* Nicht-triviale Lösungen
    loop at is_input-parts into lv_part
      where table_line < is_input-sum.
      data(lv_tabix) = sy-tabix.

* Wir entfernen je ein Element und rekurrieren
      data(ls_input) = is_input.
      delete ls_input-parts index sy-tabix.
      subtract lv_part from ls_input-sum.
      if lines( ls_input-parts ) > 1.
* Tabelle hat noch mehr als 1 part - Rekursion:
        data(ls_opt) = get_best( ls_input ).
      elseif lines( ls_input-parts ) = 1.
* Nur 1 Teil, dann gibt es nur diese triviale Lösung:
        ls_opt = value #(
          sum   = ls_input-parts[ 1 ]
          parts = ls_input-parts ).
      else.
* Null Teile
        clear ls_opt.
      endif.

* Das herausgenommene Part wieder hinzufügen
      append lv_part to ls_opt-parts.
      add lv_part to ls_opt-sum.

* Schauen, was herauskam:
      if ls_opt-sum = is_input-sum.
* Exakter Match gefunden
        es_opt = ls_opt.
        return.
      elseif ls_opt-sum < is_input-sum.
* Beste Annäherung an is_input-sum in es_opt merken
        if es_opt is initial.
          es_opt = ls_opt.
        elseif ls_opt-sum > es_opt-sum.
          es_opt = ls_opt.
        endif.
      endif.

    endloop.

  endmethod.
endclass.


start-of-selection.
  lcl_opt=>start( ).