-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
    27 окт 2022 в 6:11
  • 2
    575+1000+1425=3000 точно. А так - чистой воды задача линейного раскроя.
    – Akina
    27 окт 2022 в 6:29
  • суммы должны быть не больше или равны. И что такое "линейный раскрой"?
    – woojin
    27 окт 2022 в 11:05
  • ru.wikipedia.org/wiki/…
    – Alekcvp
    27 окт 2022 в 11:06
  • суммы должны быть не больше или равны. Ну знаешь... 360+360=720 < 3000 - что, тоже пойдёт как вариант?
    – Akina
    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;

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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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