-1

Как можно найти оптимальное количество сумм элементов массива, но каждая сумма не должна превышают 3000 в массиве 50 элементов (может быть больше, может быть меньше)

var
  len: TArray<integer>;
  len := [360, 360, 360, 360, 520, 520, 575, 575, 575, 575, 640, 640, 640, 640,
          960, 960, 960, 198, 198, 820, 820, 820, 820, 1425, 1425, 2270, 2270,
          2270, 2270, 2270, 2400, 2400, 1000, 1000, 1000, 1000, 1000, 1000, 1000,
          1000, 1000, 502, 502, 502, 502, 529, 562, 726, 2441, 2870];

хочется на выходе получить все возможные варианты сумм с данными массива, но что бы сумма не превышала (в данный момент) 3000 пример:
len[49] = 2870 - очень близко с 3000, ни каких суммирований произвести не возможно
len48 + len45 = 2970 - первая сумма, которая так же близка к 3000
и т.д.

должно быть примерно так (ручками посчитал), у меня получилось 17 вариантов сложения данных, возможно программа найдёт меньшее количество или наоборот большее:

(0)     2870 = 2870
(1)     2441 + 529 = 2970
(2)     2400 + 575 = 2975
(3)     2400 + 575 = 2975
(4)     2270 + 726 = 2996
(5)     2270 + 640 = 2910
(6)     2270 + 640 = 2910
(7)     2270 + 640 = 2910
(8)     2270 + 640 = 2910
(9)     1425 + 1425 = 2850
(10)    1000 + 1000 + 1000 = 3000
(11)    1000 + 1000 + 1000 = 3000
(12)    1000 + 1000 + 1000 = 3000
(13)    960 + 960 + 960 = 2880
(14)    820 + 820 + 820 + 520 = 2980
(15)    820 + 575 + 575 + 562 + 360 = 2892
(16)    520 + 502 + 502 + 502 + 502 + 360 = 2888
(17)    360 + 360 + 198 + 198 = 1116
14
  • 3
    Просто максимально приближенные и не превышающие - это разные вещи. К тому же неплохо бы определить чёткий критерий этой приближенности - скажем, в форме максимально допустимого отклонения.
    – Akina
    Commented 27 окт. 2022 в 6:11
  • 2
    575+1000+1425=3000 точно. А так - чистой воды задача линейного раскроя.
    – Akina
    Commented 27 окт. 2022 в 6:29
  • суммы должны быть не больше или равны. И что такое "линейный раскрой"?
    – woojin
    Commented 27 окт. 2022 в 11:05
  • ru.wikipedia.org/wiki/…
    – Alekcvp
    Commented 27 окт. 2022 в 11:06
  • суммы должны быть не больше или равны. Ну знаешь... 360+360=720 < 3000 - что, тоже пойдёт как вариант?
    – Akina
    Commented 27 окт. 2022 в 11:09

1 ответ 1

0

в общем у меня получилось как то так:

type
  TIntArr = TArray<integer>;

var
  len, len2, len3: TIntArr;

begin
procedure summ(var mas: TIntArr);
  function SumIsBig(x, y: integer; out resul: integer): boolean;
  begin
    resul := x + y;
    Result := resul > 3000;
  end;

  function resize(var arr: TIntArr; idx: integer): Boolean;
  var
    k: integer;

  begin
    for k := idx to High(arr) - 1 do
      arr[k] := arr[k + 1];
    SetLength(arr, Length(arr) - 1);

    Result := True;
  end;

var
  i, j, idx: integer;
  sum: integer;
  reslt: integer;
  resz: Boolean;

begin
  idx := 0;
  i := Low(mas);
  while Low(mas) < High(mas) - 1 do
    begin
      sum := mas[0];

      j := 1;
      while j <= High(mas) do
        begin
          if not SumIsBig(sum, mas[j], reslt) then
            begin
              sum := reslt;
              resz := resize(mas, j);
            end
          else
            begin
              Inc(j);
            end;
        end;

      resize(mas, 0);

      SetLength(res, Length(res) + 1);
      res[idx] := sum;
      Inc(idx);

      Inc(i);
    end;
end;

summ(len);

end;

делал в консольке

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.