Набор суммы минимальным числом слагаемых , динамическое программирование

Ув. коллеги
Решила (кое-как) задачу с помощью ДП, но как-то тупо, тройным циклом, полностью заполняя всю трёхмерную таблицу.
Можно ли не всю таблицу заполнять, или вообще двумерной таблицей обойтись?

Задача NP-полная, псевдополиномиальная.
Условие.
Дано N целых положительных слагаемых, целое положительное число B.
Вопрос.
Набрать сумму, минимально отклоняющуюся от B (с недостатком). Если таких наборов несколько, выбрать решение с минимальным числом слагаемых.
Или так: набрать заданный вес как можно ближе по недостатку, используя минимальное число камней.

Решение.
Функция T[i,j,k] равна 1, если вес j можно набрать первыми i слагаемыми, используя не более k слагаемых.
Иначе - нулю. Три параметра у функции, вот уже и трёхмерная таблица.
Реккурентные соотношения.
Если вес i-го слагаемого M[i] не превосходит набираемой суммы j, то
T[i, j, k]:= max{T[i - 1, j, k], T[i - 1, j - M[i], k-1]}
иначе T[i, j, k]:= T[i - 1, j, k]

Консольное приложение в Делфи7. Не могу вернуть комментариям читаемый вид, увы.
Вроде работает. Выдает ближайший к заданной сумме минимальный набор.

const
    N=5; //êîëè÷åñòâî ñëàãàåìûõ
    Ves=16; //íàáèðàåìûé âåñ
    Ks=4;   //îãðàíè÷åíèå íà ÷èñëî ñëàãàåìûõ
    var
    M: array[1..N] of integer;//âåñà ñëàãàåìûõ
    //T= 1 åñëè âåñ íàáðàí, T= 0 - â ïðîòèâíîì ñëó÷àå
    //0..N - èç ñêîëüêè ïåðâûõ ñëàãàåìûõ ìîæíî íàáèðàòü ñóììó
    //0..Ves - êàêîé âåñ íóæíî íàáðàòü
    //0..Ks - ñêîëüêî ñëàãàåìûõ ìîæíî âçÿòü
    T:array[0..N,0..Ves,0..Ks] of byte;
    sum,i,j,v,k,kmin:integer;
begin
    M[1]:= 4; M[2]:= 4; M[3]:= 3; M[4]:= 7; M[5]:= 3;
 
    //íåíóëåâîé âåñ èç 0 ñëàãàåìûõ íå íàáåðåøü
    for j := 1 to Ves do
      for k := 1 to Ks do
        T[0, j, k] := 0;
 
    for i := 1 to  N do
      for j:=1 to Ves do
        T[i, j, 0] := 0;
 
    for j := 1 to Ves do
        T[0, j, 0] := 0;
 
    //íóëåâîé âåñ âñåãäà ìîæíî íàáðàòü
    for i:= 0 to  N do
      for k:=0 to Ks do
        T[i, 0, k] := 1;
 
    for i := 1 to N do begin
      for j := 1 to Ves do begin
        for k:=1 to Ks do
        //i-å ñëàãàåìîå íå ïðåâîñõîäèò íàáèðàåìóþ ñóììó
        if j >= M[i] then begin
          //i-å ñëàãàåìîå â ðàçáèåíèå íå âõîäèò
          if  T[i - 1, j, k]> T[i - 1, j - M[i], k-1] then
             T[i, j, k]:= T[i - 1, j, k]
          //äîáàâëÿåì i-å ñëàãàåìîå ê ðåøåíèþ
          else T[i, j, k]:= T[i - 1, j - M[i], k-1]; end
        //i-å ñëàãàåìîå áîëüøå íàáèðàåìîé ñóììû
        else T[i, j, k]:= T[i - 1, j, k];
      end;
    end;
 
    for j:= Ves downto 1 do
      //ìîæåì íàáðàòü ñóììó j ñ îãðàíè÷åíèåì íà Ks ñëàãàåìûõ
      if T[N, j, Ks] = 1 then
        begin
          //èùåì ðàçáèåíèå j íà ìèíèìàëüíîå ÷èñëî ñëàãàåìûõ
          for i:= Ks downto 1 do
            if T[N, j, i]=1 then k:=i;
          kmin:=k;
 
          //âîññòàíàâëèâàåì ðàçáèåíèå j íà ìèíèìàëüíîå ÷èñëî ñëàãàåìûõ
          sum:= j;  v:=0;
          for i:= N downto 1 do
            begin
            //i-å ñëàãàåìîå íå âîøëî â ðàçáèåíèå
            if (T[i, sum, k] = T[i - 1, sum, k]) or (sum=0)then
              writeln (i,'---No')
            //i-å ñëàãàåìîå âîøëî â ðàçáèåíèå
            else if sum>0 then
              begin
                writeln (i,'   ',M[i]);
                //óìåíüøèëè ñóììó
                sum := sum - M[i];
                v:=v+M[i];
                //óìåíüøèëè êîëè÷åñòâî èñïîëüçóåìûõ ñëàãàåìûõ
                k:=k-1;
              end;
             end;
          break;
        end;
    writeln('summa=',v, ' count=', kmin);
    readln;
end.

Набор сумм минимальным количеством монет при условии неограниченного числа монет каждого номинала.
Если условие не соблюдено, возможна модификация.

function NaborSummMinColMonet(const Data: array of Integer; Sum: Integer; List: TStrings): Integer;
var
  X, i, j, MinData: Integer;
  A: array of Integer;
  AList: array of string;
begin
  List.Clear;
  SetLength(A, Sum + 1);
  SetLength(AList, Sum + 1);
  MinData := MinIntValue(Data);
  for i := 0 to High(Data) do begin
    X := Data[i];
    if X > Sum then
      Break;
    A[X] := 1;
    AList[X] := IntToStr(X);
    for j := MinData to Sum - X do
      if A[j] <> 0 then
        if (A[j + X] = 0) or (A[j + X] > A[j]) then begin
          A[j + X] := A[j] + 1;
          AList[j + X] := AList[j] + ' ' + IntToStr(X);
        end;
  end;
  Result := A[Sum];//минимальное количество монет, которым набрана Sum
 
  //номиналы монет, которыми набраны возможные суммы до Sum включительно
  for i := 1 to Sum do
    if A[i] <> 0 then
       List.Add(Format('Sum %d Cnt: %d Vals: %s',[i, A[i], AList[i]]));
end;
 
procedure TForm1.Button18Click(Sender: TObject);
begin
  NaborSummMinColMonet([3, 6, 13], 20, Memo1.Lines);
end;
 
 
Sum 3 Cnt: 1 Vals: 3
Sum 6 Cnt: 1 Vals: 6
Sum 9 Cnt: 2 Vals: 3 6
Sum 12 Cnt: 2 Vals: 6 6
Sum 13 Cnt: 1 Vals: 13
Sum 15 Cnt: 3 Vals: 3 6 6
Sum 16 Cnt: 2 Vals: 3 13
Sum 18 Cnt: 3 Vals: 6 6 6
Sum 19 Cnt: 2 Vals: 6 13

const
N=5; //количество слагаемых
   Ves=16; //набираемый вес
   Ks=4;   //ограничение на число слагаемых
   var
   M: array[1..N] of integer;//веса слагаемых
   //T= 1 если вес набран, T= 0 - в противном случае
   //0..N - из скольки первых слагаемых можно набирать сумму
   //0..Ves - какой вес нужно набрать
   //0..Ks - сколько слагаемых можно взять
   T:array[0..N,0..Ves,0..Ks] of byte;
   sum,i,j,v,k,kmin:integer;
begin
   M[1]:= 4; M[2]:= 4; M[3]:= 3; M[4]:= 7; M[5]:= 3;
 
   //ненулевой вес из 0 слагаемых не наберешь
   for j := 1 to Ves do
     for k := 1 to Ks do
       T[0, j, k] := 0;
 
   for i := 1 to  N do
     for j:=1 to Ves do
       T[i, j, 0] := 0;
 
   for j := 1 to Ves do
       T[0, j, 0] := 0;
 
   //нулевой вес всегда можно набрать
   for i:= 0 to  N do
     for k:=0 to Ks do
       T[i, 0, k] := 1;
 
   for i := 1 to N do begin
     for j := 1 to Ves do begin
       for k:=1 to Ks do
       //i-е слагаемое не превосходит набираемую сумму
       if j >= M[i] then begin
         //i-е слагаемое в разбиение не входит
         if  T[i - 1, j, k]> T[i - 1, j - M[i], k-1] then
            T[i, j, k]:= T[i - 1, j, k]
         //добавляем i-е слагаемое к решению
         else T[i, j, k]:= T[i - 1, j - M[i], k-1]; end
       //i-е слагаемое больше набираемой суммы
       else T[i, j, k]:= T[i - 1, j, k];
     end;
   end;
 
   for j:= Ves downto 1 do
     //можем набрать сумму j с ограничением на Ks слагаемых
     if T[N, j, Ks] = 1 then
       begin
         //ищем разбиение j на минимальное число слагаемых
         for i:= Ks downto 1 do
           if T[N, j, i]=1 then k:=i;
         kmin:=k;
 
         //восстанавливаем разбиение j на минимальное число слагаемых
         sum:= j;  v:=0;
         for i:= N downto 1 do
           begin
           //i-е слагаемое не вошло в разбиение
           if (T[i, sum, k] = T[i - 1, sum, k]) or (sum=0)then
             writeln (i,'---No')
           //i-е слагаемое вошло в разбиение
           else if sum>0 then
             begin
               writeln (i,'   ',M[i]);
               //уменьшили сумму
               sum := sum - M[i];
               v:=v+M[i];
               //уменьшили количество используемых слагаемых
               k:=k-1;
             end;
            end;
         break;
       end;
   writeln('summa=',v, ' count=', kmin);
   readln;
end

Пасибки! Пока обедала , сообразила, как сократить число параметров до двух.
Щас новую прожку напишу, а потом нагло полезу на готовое.

Теперь функция T[i,j] возвращает минимальное число слагаемых в наборе веса j первыми i слагаемыми;
T[i,j]= +бесконечность, если вес набрать нельзя.

Реккурентные соотношения
T[i,0]= 0 при i>=0
T[0,j]= +бесконечность при j>=1
Если вес i-го слагаемого M[i] не превосходит набираемой суммы j, то
T[i, j]:= min{T[i - 1, j], T[i - 1, j - M[i]]+1}
иначе T[i, j]:= T[i - 1, j]

const
    N=5; //количество слагаемых
    Ves=16; //набираемый вес
    inf=100;//+бесконечность)))
    var
    M: array[1..N] of integer;//веса слагаемых
    //T= мин. число слагаемых в наборе веса;
    //если вес набрать нельзя T= +бесконечность
    //0..N - из скольки первых слагаемых можно набирать сумму
    //0..Ves - какой вес нужно набрать
    T:array[0..N,0..Ves] of byte;
    sum,i,j,v,k,kmin:integer;
begin
    M[1]:= 4; M[2]:= 4; M[3]:= 3; M[4]:= 7; M[5]:= 3;
 
    //ненулевой вес из 0 слагаемых не наберешь
    for j:= 1 to Ves do
      T[0, j]:= inf;
 
    //нулевой вес можно набрать 0 слагаемых
    for i:= 0 to  N do
      T[i, 0] := 0;
 
    for i := 1 to N do begin
      for j := 1 to Ves do begin
        //i-е слагаемое не превосходит набираемую сумму
        if j > M[i] then begin
          //i-е слагаемое в разбиение не входит
          if  T[i - 1, j]< T[i - 1, j - M[i]]+1 then
             T[i, j]:= T[i - 1, j]
          //добавляем i-е слагаемое к решению
          else T[i, j]:= T[i - 1, j - M[i]]+1; end
        //i-е слагаемое больше набираемой суммы
        else if j < M[i] then T[i, j]:= T[i - 1, j]
        //набор суммы одним слагаемым
        else T[i, j]:=1;
      end;
    end;
 
    for j:= Ves downto 1 do
      //можем набрать сумму j
      if T[N, j]< inf then
        begin
          kmin:=T[N,j];
          //восстанавливаем разбиение j на минимальное число слагаемых
          sum:= j;  v:=0;
          for i:= N downto 1 do
            begin
            //i-е слагаемое не вошло в разбиение
            if (T[i, sum] = T[i - 1, sum]) or (sum=0)then
              writeln (i,'---No')
            //i-е слагаемое вошло в разбиение
            else if sum>0 then
              begin
                writeln (i,'   ',M[i]);
                //уменьшили сумму
                sum := sum - M[i];
                v:=v+M[i];
              end;
             end;
          break;
        end;
    writeln('summa=',v, ' count=', kmin);
    readln;
 
end.

Сообщение отредактировано: Swetlana - 30.08.11, 11:46

MBo, посмотрела.
То, что для суммы, набираемой одной монетой, не надо вычислять, исправила.

Скрытый текст

Вообще-то, я додумалась, но чёто поленилась сразу код исправлять

Правильно я поняла, что двумерная табличка нужна только для восстановления решения?
То есть у тебя массив A одномерный, т.к. сразу запоминаем разбиение?

>массив A одномерный, т.к. сразу запоминаем разбиение?
Да. Переделывал из другой задачи, имена существенных переменных сразу не сделал нормальными
A - BestCounts
AList - BestValuesList

И возвращаемые значения - не совсем то, что по условию.

Нужный результат - в последнем ненулевом элементе A (и соотв. AList). Его индекс - максимальная сумма, не превосходящая заданную, которую можно набрать из данного комплекта.

В А - количество слагаемых (минимально требуемое)
В AList - строка с самим разбиением, набором слагаемых (одним из, если их несколько)

По сути - восходящее ДП.

>X := Data[i];
Очередной номинал

>A[X] := 1;
Это суммы, выражаемые одной монетой, что, безусловно, выгодно всегда.

> if A[j] <> 0 then
учитываем только ненулевые предсуммы

> if (A[j + X] = 0) or (A[j + X] > A[j]) then begin
Если сумма j + X еще не встречалась, либо в лучшем до сих пор случае набрана не меньшим количеством монет, чем это возможно с использованием монеты X

Вообще-то восстановить решение тоже можно по одномерной.

Вроде недавно уже была такая задача.

Вот вариант с восстановлением пути

function NaborSummMinColMonet2(const Data: array of Integer; Sum: Integer):string;
var
  X, i, j, MinData: Integer;
  BestCounts: array of Integer;
  BackLook: array of Integer;
begin
  SetLength(BestCounts, Sum + 1);
  SetLength(BackLook, Sum + 1);
  MinData := MinIntValue(Data);
  for i := 0 to High(Data) do begin
    X := Data[i];
    if X > Sum then
      Break;
    BestCounts[X] := 1;
    BackLook[X] := 0;
    for j := MinData to Sum - X do
      if BestCounts[j] <> 0 then
        if (BestCounts[j + X] = 0) or (BestCounts[j + X] > BestCounts[j]) then begin
          BestCounts[j + X] := BestCounts[j] + 1;
          BackLook[j + X] := j;
        end;
  end;
 
  i := Sum;
  while (i >= 0) and (BestCounts[i] = 0) do
    Dec(i);
 
  while i <> 0 do begin
    Result := Result + IntToStr(i - BackLook[i]) + ' ';
    i := BackLook[i];
  end;
end;

Пасибки, щас буду сравнивать твой второй и мой третий.
Думала, как отказаться от двумерных массвов, и завела дополнительную функцию L.
Теперь у меня функция T одномерная, аргумент - набираемая сумма, T[j] - min число слагаемых.
L[j] - номер последнего слагаемого, использованного для набора суммы j.
Задача с неограниченным числом слагаемых решилась сразу, а вот с ограниченным что-то не получается...

Размен суммы (или ближайшей к ней с недостатком) минимальным количеством монет, в неограниченном количестве

const
    N=3; //количество слагаемых
    Ves=19; //набираемый вес
    inf=100;//+бесконечность)))
    var
    //веса слагаемых в порядке возрастания, количество экземпляров не ограничено
    M: array[1..N] of integer;
    //T= мин. число слагаемых в наборе веса;
    //если вес набрать нельзя T= +бесконечность
    //0..Ves - какой вес нужно набрать
    T:array[0..Ves] of byte;
    //номер последнего слагаемого, использованного для набора веса
    L: array[0..Ves] of byte;
    sum,i,j,v,k,kmin:integer;
begin
    M[1]:= 2; M[2]:= 4; M[3]:= 6;
 
    //инициализация
    T[0]:= 0; L[0]:=0;
    for j:= 1 to Ves do
      T[j]:= inf;
 
    for j := 1 to Ves do
      for i := 1 to N do
        begin
          //i-е слагаемое не превосходит набираемую сумму
          if (j > M[i])and(T[j - M[i]]<inf) then
            begin
              //добавляем i-е слагаемое к решению
              //и запоминаем его номер
              if  T[j]> T[j - M[i]]+1 then
                begin
                  T[j]:= T[j - M[i]]+1; L[j]:= i;
                end
            end
          //i-е и все последующие слагаемые больше набираемой суммы
          else if (j < M[i]) then break
          //минимальный набор суммы одним слагаемым
          else if (j= M[i]) then
            begin
              T[j]:= 1; L[j]:= i; break;
            end;
        end;
    //восстановление разбиения
    for j:= Ves downto 1 do
      //можем набрать сумму j
      if T[j]< inf then
        begin
          kmin:=T[j];
          //восстанавливаем разбиение j на минимальное число слагаемых
          sum:= j;  v:=0;
          while sum<>0 do
            begin
              i:= L[sum];//i-е слагаемое вошло в разбиение
              writeln (M[i],' ');
              //уменьшили сумму
              sum := sum - M[i];
              v:=v+M[i];
            end;
          break;
        end;
    writeln('summa=',v, ' count=', kmin);
    readln;
 
end.

Добавлено 30.08.11, 20:54

Цитата amk @ 30.08.11, 12:53

Вообще-то восстановить решение тоже можно по одномерной.

Вроде недавно уже была такая задача.

Я уезжала, видимо, чего-то упустила...

Сообщение отредактировано: Swetlana - 30.08.11, 20:57

>Теперь у меня функция T одномерная, аргумент - набираемая сумма, T[j] - min число слагаемых.
L[j] - номер последнего слагаемого, использованного для набора суммы j.

Угу, теперь по сути наши алгоритмы близки.


>а вот с ограниченным что-то не получается
Тут надо подумать, как будет время - для неограниченного сильно облегчает жизнь то, что сумма с бОльшим числом слагаемых заменяется лучшим вариантом безусловно, т.к. она ни в коем случае не понадобится, а для ограниченного в этом я сомневаюсь.

Цитата MBo @ 31.08.11, 03:18

Угу, теперь по сути наши алгоритмы близки.


>а вот с ограниченным что-то не получается
Тут надо подумать, как будет время - для неограниченного сильно облегчает жизнь то, что сумма с бОльшим числом слагаемых заменяется лучшим вариантом безусловно, т.к. она ни в коем случае не понадобится, а для ограниченного в этом я сомневаюсь.

Ага, только мне ещё подправить нужно - суммы набирать, начиная с веса минимального слагаемого.
Написала, наконец, с подказками

В неограниченных весах вначале цикл по набираемым суммам. Фиксируем сумму, для неё прогоняем все подходящие по весу слагаемые. То есть не фиксируем, было взято это слагаемое раньше или нет.
А в варианте с двумерной табличкой удалённый параметр (из скольки первых i слагаемых делаем набор) как раз выполнял эту функцию...

MBo, ценный алгоритм, задача о рюкзаке с неограниченным количеством предметов влёт решается.
Для тех, кто в гугле, приведу формулировку.

РЮКЗАК С КРАТНЫМ ВЫБОРОМ ЭЛЕМЕНТОВ
Условие. Задано конечное множество предметов, положительные целые стоимости и веса каждого предмета, полож.целое ограничение на вес рюкзака.
Вопрос. Можно ли сопоставить каждому предмету целую положительную кратность так, чтобы суммарный вес всех предметов с учётом кратностей не превосходил общее ограничение на вес рюкзака, а суммарная ценность была максимальной.

const
    N=3; //количество предметов
    Ves=8; //ограничение на вес рюкзака
    var
    //веса предметов в порядке возрастания, количество экземпляров не ограничено
    M: array[1..N] of integer;
    //стоимости предметов
    C: array[1..N] of integer;
    //T= максимальная ценность рюкзака данного веса
    //если вес набрать нельзя, T=0
    T:array[0..Ves] of integer;
    //номер последнего слагаемого, вошедшего в рюкзак данного веса
    L: array[0..Ves] of byte;
    sum,i,j,v,k,Cmax:integer;
begin
    M[1]:= 2; M[2]:= 4; M[3]:= 6;
    C[1]:= 2; C[2]:= 5; C[3]:= 6;
    //инициализация
    for j:= 0 to Ves do
      begin T[j]:= 0; L[j]:=0; end;
 
    for j := M[1] to Ves do
      for i := 1 to N do
        begin
          if (T[j]<C[i]) and (j=M[i]) then
            //набираем вес одним предметом
            begin
              T[j]:= C[i]; L[j]:=i;
            end
          //i-е слагаемое не превосходит набираемую сумму
          //и набор веса j - M[i] уже существует
          else if (j >= M[i])and (T[j - M[i]]>0) then
            begin
              //добавляем i-е слагаемое к решению
              //и запоминаем его номер
              if  T[j]< T[j - M[i]]+ C[i] then
                begin
                  T[j]:= T[j - M[i]]+C[i]; L[j]:= i;
                end
            end
          //i-е и все последующие слагаемые больше набираемой суммы
          else if (j < M[i]) then break;
        end;
 
    Cmax:=0; sum:=0;
    //ищем максимум стоимости
    for j:= Ves downto 1 do
      if T[j]> Cmax then
        begin Cmax:=T[j]; sum:=j; end;
    
    //восстанавливаем содержимое максимально ценного рюкзака
    v:=0; k:=0;
    while sum<>0 do
      begin
        i:= L[sum];//i-е слагаемое вошло в рюкзак
        writeln (M[i],' ');
        //уменьшили сумму
        sum := sum - M[i];
        v:=v+M[i]; k:= k+C[i];
      end;
    writeln('Cmax=', k,' ves=',v);
    readln;
end.

Добавлено 31.08.11, 07:43
Залезла в лекции Котова по ДП)
Для задачи о наборе веса (пример1 в цитате) любым, не минимальным, количеством заданных слагаемых, приводится способ, как избавится от двумерного массива.

----------
Использование двумерной матрицы в примере 1 позволяет восстановить структуру решения. Однако из правила вычисления элементов таблицы видно, что для вычисления значений в текущей строке достаточно знать значения только в предыдущей строке. Более того, значения очередной строки можно вычислить, прямо на месте предыдущей. Это можно сделать, если вычислять значения элементов не слева направо, а справа налево, т.е. идя с конца массива в начало. Дело в том, что если вычислять значения элементов слева направо, то возможно многократное использование массы некоторого предмета в наборе, тогда как при вычислении справа налево это невозможно. Поэтому, для вычисления значения функции Т достаточно использовать одномерный массив, размер которого ограничен требуемой суммарной массой плюс 1, вначале, значение нулевого элемента равно 1, а всех остальных равно 0.

T[0] := 1;
for i:=1 to 5 do
T[i] := 0;
for i:=1 to 5 do
for j:=16 downto M[i] do
T[j] := max(T[j], T[j - M[i]]);

Однако при этом уже невозможно прямо восстановить структуру решения. Чтобы устранить этот недостаток, обычно используется подход, при котором для каждой позиции запоминается позиция-предшественник, из которой мы в нее попали в текущую позицию. Эта позиция определяется аргументом, на котором достигаемся оптимум (максимум, минимум) рассматриваемой функции. В данном случае для каждой позиции i можно определить номер первого предмета, для которого значение Т(i, j) стало максимальным (в данном случае равным единице).
{Вычисление значений и запоминание предшественника (Father)}
T[0] := 1;
Father[0]:=0
for j:=1 to 16 do
begin
T[j] := 0;
Father[j]:=0
end;
for i:=1 to 5 do
for j:=16 to M[i] do
if T[j] < T[j - M[i]] then
begin
T[j] := T[j - M[i]] ;
Father[j]:=i;
end;



{Восстановление решения}
sum:=16;
i:= Father[sum];
While (i>0) do
Begin
Writeln(i);
sum:=sum-M[i];
i:= Father[sum];
End;
--------------------

Сообщение отредактировано: Swetlana - 31.08.11, 11:29

Подправила в цитате из Котова опечатку, в первом фрагменте кода. Вообще, в этой задаче, про набор суммы, сплошные опечатки. Ладно.

Набор суммы минимальным числом заданных слагаемых.
Вариант с одномерными массивами.
Вначале код

const
    N=5; //количество слагаемых
    Ves=6; //набираемый вес
    inf=100;//+бесконечность)
    var
    //веса слагаемых, отсортированных по возрастанию
    M: array[1..N] of integer;//веса слагаемых
    //T= мин. число слагаемых в наборе веса;
    //если вес набрать нельзя T= +бесконечность
    T:array[0..Ves] of byte;
    //номер последнего слагаемого, вошедшего в набор веса
    L:array[0..Ves] of byte;
    sum,i,j,v,k,kmin:integer;
begin
    M[1]:= 3; M[2]:= 4; M[3]:= 4; M[4]:= 4; M[5]:= 7;
 
    //нулевой вес набирается нулём слагаемых
    T[0]:=0; L[0]:=0;
    //ненулевой вес пока не набран
    for j:= 1 to Ves do
      T[j]:= inf;
 
    for i := 1 to N do
      for j := Ves downto M[1] do
        begin
          //i-е слагаемое не превосходит набираемую сумму
          if M[i] < j then
            begin
              //добавляем i-е слагаемое к решению
              if  T[j] > T[j - M[i]]+1 then
                begin
                  T[j]:= T[j - M[i]]+1; L[j]:=i;
                end
            end
          //i-е слагаемое больше набираемой суммы и всех последующих
          else if M[i] > j then break
          //набор суммы одним слагаемым
          else
            begin T[j]:=1; L[j]:= i; end;
        end;
 
    for j:= Ves downto 1 do
      //можем набрать сумму j
      if T[j]< inf then
        begin
          kmin:=T[j];
          //восстанавливаем разбиение j на минимальное число слагаемых
          sum:= j;  v:=0;
          while sum<>0 do
            begin
              i:= L[sum];
              writeln (M[i]);
              //уменьшили сумму
              sum := sum - M[i];
              v:=v+M[i];
            end;
          break; //сумма набрана ну и слава тебе, Господи
        end;
    writeln('summa=',v, ' count=', kmin);
    readln;
end.

-------------------------------------------------------------------
Разберём способ заполнения массива T
следующими циклами

Цитата

for i := 1 to N do
for j := Ves downto M[1] do

и реккурентными соотношениями

Цитата

T[0]:=0; L[0]:=0;
//ненулевой вес пока не набран
for j:= 1 to Ves do
T[j]:= inf;

Цитата

//i-е слагаемое не превосходит набираемую сумму
if M[i] < j then
begin
//добавляем i-е слагаемое к решению
if T[j] > T[j - M[i]]+1 then
begin
T[j]:= T[j - M[i]]+1; L[j]:=i;
end
end
//i-е слагаемое больше набираемой суммы и всех последующих
else if M[i] > j then break
//набор суммы одним слагаемым
else
begin T[j]:=1; L[j]:= i; end;

Добавлено 31.08.11, 11:48
Слагаемые отсортированы по возрастанию. Фиксируем минимальное слагаемое, в программе это 3.
Цикл весов прокручивается впустую, от больших к меньшим, пока не достигает минимального веса 3.
Записываем T[3]=1.
Первое слагаемое вышло, в дальнейшем слагаемое 3 для набора суммы уже не доступно. В разложение больших весов оно может попасть только как решение подзадачи "набрать вес 3 минимальным числом слагаемых".
Аналогично фиксируем второе слагаемое 4, прокручиваем цикл с весами и записываем T[4]=1.
Веса 5 и 6 набрать нельзя, для них значение T равно +бесконечности.
Если поменять циклы таким образом

Цитата

for j := M[1] to Ves do
for i := 1 to N do

то при наборе веса 6 слагаемое 3 можно было бы использовать второй раз, и 6 было бы набрано как 3+3.
Итак, набираем весь 7, текущее слагаемое - 4 (их в наборе несколько). 7-4=3. Смотрим решение подзадачи T[3].
Она уже решена, поэтому T[7]=1+T[3]=2.

Добавлено 31.08.11, 12:08
Если поменять циклы таким образом

Цитата

for i := 1 to N do
for j := M[1] to Ves do

то 3 будет использоваться многократно, т.к. при фиксированном значении слагаемого 3 в одном проходе
суммы набираются от меньшего к большему. Т.е. вначале набираем сумму 3 с помощью тройки. Потом при наборе 6 опять используем 3 (текущее слагаемое) + решение подзадачи T[3].

Одним словом, чтобы разобраться, надо поэкспериментировать с циклами, попереставлять их то так, то эдак

Сообщение отредактировано: Swetlana - 31.08.11, 12:08

Помогите пожалуйста.
Нужно набрать сумму, но с заданным числом слагаемых(с повторениями).
Заранее спасибо.

>Нужно набрать сумму, но с заданным числом слагаемых(с повторениями).
Это всё условие, ничего не упущено?

Все остальные условия остаются как в предыдущих постах.
Другими словами:
Условие.
Дано N целых положительных слагаемых, целое положительное число B.
Вопрос.
Набрать сумму, минимально отклоняющуюся от B (с недостатком). Если таких наборов несколько, выбрать решение с минимальным числом слагаемых. Выбрать вариант с заданным числом слагаемых.

можно построить решение динамическим программированием - заполнить двумерную таблицу из M строк и B столбцов, где M - число слагаемых.

Цитата

можно построить решение динамическим программированием - заполнить двумерную таблицу из M строк и B столбцов, где M - число слагаемых.

А на каком этапе определять количество слагаемых?

Добавлено 05.09.11, 10:22

Цитата

Цитата
можно построить решение динамическим программированием - заполнить двумерную таблицу из M строк и B столбцов, где M - число слагаемых.

А на каком этапе определять количество слагаемых?

я имею ввиду как определить в какую именно строку записывать слагаемое

безо всякой оптимизации со сложностью O(NMonet * Sum * Length(Data))

function NaborSummZadColMonet(const Data: array of Integer; NMonet, Sum: Integer):string;
var
  i, j, k: Integer;
  A: array of array of Integer;
begin
  SetLength(A, NMonet + 1, Sum + 1);
 
  for k := Low(Data) to High(Data) do
    if Data[k] <= Sum then
      A[1, Data[k]] := Data[k];
 
  for i := 2 to NMonet do
    for j := 1 to Sum do
      if A[i - 1, j] > 0 then
        for k := Low(Data) to High(Data) do
          if j + Data[k] <= Sum then
            A[i, j + Data[k]] := Data[k];
 
 
  i := Sum;
  while (i >= 0) and (A[NMonet, i] = 0) do
    Dec(i);
 
  for j := NMonet downto 1 do begin
    Result := Result + IntToStr(A[j, i]) + ' ';
    i := i - A[j, i];
  end;
end;
 
 
NaborSummZadColMonet([3, 5], 6, 29) даст 3 5 5 5 5 5 (шестью монетами можно набрать 28)

Это великолепно!!!
Огромнейшее спасибо. Вы даже не представляете как помогли мне.

Единственное улучшение, можно обойтись одномерным массивом (ну или двумерным, но один из размеров фиксированный). Переменный - набираемая сумма. В каждом элементе хранить последнюю добавленную монету. Можно заметно ускорить, если номиналов монет мало по сравнению с количеством монет, храня также количество добавленных монет. Тогда потребуется число проходов, равное количеству номиналов.

N = 28 # Набираемая сумма
T = [(0, 0) for i in range(N+1)]
M = (5, 3)
T[0] = (0, 1)
for m in M:
  for i in range(N-m+1):
    if T[i][1] and not T[i+m][1]:
      if T[i][0] == m:
        T[i+m] = (m, T[i][1] + 1)
      else:
        T[i+m] = (m, 1)
n = N
while not T[n]:
  n -= 1
while n > 0:
  print(T[n][1], "монет достоинства", T[n][0])
  n -= T[n][0]*T[n][1]

Сообщение отредактировано: amk - 05.09.11, 17:44

Пыталась написать одномерным массивом, но не получилось То ли ДП тяжело даётся, то ли на работу после отпуска тяжело выходить. А вот если выкинуть эти массивы, и писать честной-благородной рекурсией, то даже думать не нужно.
Тока рекурсией наберётся одна-единственная заданная сумма, поэтому слова "или ближайшую к ней" из песни придётся выкинуть.

Ну мой пример (Python), используя "массив" (N+1)*2, набирает наиболее близкую сумму за два прохода (два вида монет) по массиву. Правда как только я его написал, он у меня сразу за пределы массива вылетел, пришлось проходы немного укоротить.
При необходимости количество монет каждого номинала можно ограничить.
В списке монет порядок задает предпочтение по их использованию.

Добавлено 05.09.11, 18:23
Рекурсией как раз можно определить все возможные варианты. Даже если требуемая сумма недостижима. Правда, работать алгоритм будет медленнее.

До кучи - нисходящее ДП, мемоизация.
Преимущество над восходящим - полезные ячейки таблицы заполняются единожды.

Для многих вариантов начальных условий вместо массива выгоднее словарь по ключу-паре <КоличествоМонет, Сумма>

Не исключаю, что для варианта, когда ищется не единственная сумма, а ближайшая снизу, может быть полезно отмечать в массиве A недостижимые варианты.

function NaborSummZadColMonetMemoize(const Data: array of Integer; NMonet, Sum: Integer): string;
var
  A: array of array of Integer;
  j, k: Integer;
 
  function Nabor(NM, From, Summ: Integer): Integer;
  var
    i: Integer;
  begin
    Result := 0;
 
    if (Summ <= 0) or (NM <= 0) then
      Exit;
 
    for i := From to High(Data) do begin
      if Data[i] > Summ then
        Break;
      if A[NM - 1, Summ - Data[i]] <> 0 then begin
        A[NM, Summ] := Data[i];
        Result := Data[i];
        Break;
      end else
      if Nabor(NM - 1, i, Summ - Data[i]) <> 0 then begin
        A[NM, Summ] := Data[i];
        Result := Data[i];
        Break;
      end;
    end;
 
  end;
 
begin
  SetLength(A, NMonet + 1, Sum + 1);
   for k := Low(Data) to High(Data) do
     if Data[k] <= Sum then
       A[1, Data[k]] := Data[k];
 
  k := Sum;
  while (k > 0) and (Nabor(NMonet, 0, k) = 0) do
    Dec(k);
 
  Result := '';
  for j := NMonet downto 1 do begin
    Result := Result + IntToStr(A[j, k]) + ' ';
    k := k - A[j, k];
  end;
end;

Цитата amk @ 05.09.11, 18:20

Рекурсией как раз можно определить все возможные варианты. Даже если требуемая сумма недостижима. Правда, работать алгоритм будет медленнее.

Вот и нет, неправда ваша
Во-первых, в худшем случае рекурсия быстрее, чем ДП. Потому что рекурсия работает 2^n, а ДП n*2^n.
Во-вторых, рекурсия, конечно, генерирует все 2^n выборок но не запоминает.

Все зависит от конкретной задачи. Например, для набора 100 при наличии 10 чисел из диапазона 10-30, ДП-вариант оказывается быстрее.

Да и в общем случае он не требует производить n*2^n операций. Вполне можно обойтись и 2^n, если не проверять ненабранные еще суммы. Учитывая, что шаг рекурсии вообще говоря сложнее шага итерации - ДП-алгоритм оказывается несколько быстрее. Еще сильнее он ускоряется, если некоторые частичные суммы могут быть набраны несколькими способами, поскольку не проверяет варианты.

Кстати, он пригоден и при поиске суммы по модулю.

Здравствуйте! Я уже описал свою задачу в соседней теме Сумма чисел в массиве, наиболее приближающаяся к необходимой Можно ли здешнее решение переложить на мой случай? Или т.к. числа не целые то не подходит?

Цитата Rate93 @ 21.05.13, 02:04

Можно ли здешнее решение переложить на мой случай? Или т.к. числа не целые то не подходит?

Можно. Насчёт нецелости - это вопрос к определению типа переменных и точности расчётов.

Доброго времени суток!

как сделать алгоритм размена монеток чтобы он прошел максимально все номиналы монет? Может ктото делал такое просьба помочь как это сделать? спасибо за любые ответы!

Цитата test4me @ 01.07.21, 12:10

как сделать алгоритм размена монеток чтобы он прошел максимально все номиналы монет?

Начинать не с нуля, а с "каждой монеты по штуке". Если решение не найдено, следующая итерация "каждой монеты, кроме одной, по штуке"... и т.д.. до решения.

Akina
Спасибо... можно на примере не совсем понял что значит не с нуля?
допустим у меня массив номиналов {10,5,2,1} и сумма 47...
1) массив отсортировать? если да то по убыванию или возрастанию?
2) насколько я понимаю мне нужен не жадный алгоритм?

Сообщение отредактировано: test4me - 01.07.21, 14:39

постановка задачи неполная, конечно
как я понял, количество монет заданных номиналов в наличии в неограниченном количестве
как я понял, нужно "под ноль" разменять заданную сумму

1. не факт, что подобный размен вообще возможен. Сумма = 17, номиналы {4, 10} - решения нет. Не знаю, надо ли перед основными вычислениями убедиться, что решение в принципе есть (то есть найти первое, пусть неоптимальное разложение) или нужно вычислять, и, если, никакое решение не найдено, значит, разложение невозможно...Тут какая-то делимость может быть замешана. Проблема в том, что проверять придется вообще всевозможные делимости, в том числе всевозможные суммы номиналов.

2. какие номиналы брать, когда их кол-во одинаково, но их состав различен. Пример: S = 25, номиналы {11, 12, 13, 14} --> S1 = 11 + 14, S2 = 12 + 13, S1 = S2...

3. мат.модель. Обозначим номиналы так: {a, b, c, ...}. N(x) - количество монет номинала x
a * N(a) + b * N(b) + c * N© + ... S - попахивает чем-то диофантовым вроде, т к все решать надо в целых числах
надо добавить ограничения на количество монет каждого номинала
N(a) = [0 ... S/a]
N(b) = [0 ... S/b]
...

4. надо ли сортировать? а вот хз) по идее можно, по возрастанию. Сведется что-то к задаче о рюкзаке, только тебе нужен размен под ноль и никаких дельт образовываться не должно.

Я не знаю, как это решить, но такое чувство, что здесь какой-то рекурсивный перебор будет. Akina, как я понял, предложил тебе вариант подбором/перебором, возможно, это самый оптимальный подход здесь.
Пример: {1, 2, 3, 5, 10, 17, 25}, S = 200
N(1) = 200, N(2) = 100, N(3) = 66, N(5) = 40, N(10) = 20, N(17) = 11, N(25) = 8
Сколько всего здесь переборов? Вроде получается 200 * 100 * 66 * 40 * 20 * 11 * 8 (это еще нулевые значения не взяты в расчет) = 92 928 000 000 (почти 100 миллиардов вариантов перебора) ). А если S = 2 500 или 27 539? - очевидно, что в какой-то момент полным перебором за разумное время результат будет невозможно получить.

-----------------------------------------
если количество монет каждого номинала строго из множества {0; 1}, тогда все значительно упрощается, но все равно, какие-то тонкости здесь есть...

FasterHarder
Спасибо за развернутый ответ!
задача такая есть товары в количестве А но незнаем какие это товары, которые проданы за день скажем на какую то условную сумму денег.
Есть известная сумма Х по которой надо списать то количество товара которое надо найти в зависимости какой товар по цене подойдет или хотя бы приблизится к этой сумме.

Скажем есть условно 20 товаров:
А1 10 шт по цене 2
А2 6 шт по цене 3
А3 18 шт по цене 5
А4 3 шт по цене 7
А5 35 шт по цене 9
....
А20 14 шт по цене 15

Сумма известна скажем 345 условных единиц денег, надо по возможности пройтись по стоимости всех существующих товаров (пусть отсортиранных допустим по возрастанию, тут можно подумать как чередовать возможно както)
вобщем нужно какието товары выбрать пройдя по возможности охватив максимально как можно больше разных даже если они хоть по одному войдут в эту сумму или минимум приблизятся к нему. Вот эта задача.

Сообщение отредактировано: test4me - 01.07.21, 19:21

Цитата test4me @ 01.07.21, 14:12

допустим у меня массив номиналов {10,5,2,1} и сумма 47

Сразу откладываем по 1 монете. Это сумма 18. Остаётся 47-18=29. Пытаемся набрать её произвольным образом. Получается (например, 2*10+1*5+2*2+0*1). Прибавляем те самые отложенные монеты, и получаем решение (одно из возможных): 3*10+2*5+3*2+1*1=47.

Akina
Спасибо попробую сделать!

Цитата test4me @ 01.07.21, 19:16

FasterHarder
Спасибо за развернутый ответ!
задача такая есть товары в количестве А но незнаем какие это товары, которые проданы за день скажем на какую то условную сумму денег.
Есть известная сумма Х по которой надо списать то количество товара которое надо найти в зависимости какой товар по цене подойдет или хотя бы приблизится к этой сумме.

Скажем есть условно 20 товаров:
А1 10 шт по цене 2
А2 6 шт по цене 3
А3 18 шт по цене 5
А4 3 шт по цене 7
А5 35 шт по цене 9
....
А20 14 шт по цене 15

Сумма известна скажем 345 условных единиц денег, надо по возможности пройтись по стоимости всех существующих товаров (пусть отсортиранных допустим по возрастанию, тут можно подумать как чередовать возможно както)
вобщем нужно какието товары выбрать пройдя по возможности охватив максимально как можно больше разных даже если они хоть по одному войдут в эту сумму или минимум приблизятся к нему. Вот эта задача.

У вас тут два критерия.
Во-первых, включить все разновидности товаров в набор суммы. Во-вторых, максимально приблизиться к требуемой сумме.
Может оказаться так, что сумма точно набирается, но без одного товара. А с этим товаром она точно не набирается. Или сумма точно набирается только одним видом товара.
Так что вы определитесь, что вам важнее: минимизация отклонения или включение всех видов товаров.
Если второе, то сразу берите по одной штуке каждого товара. Затем просто решается задача о наборе суммы.

Решение этой задачи зависит от величины набираемой суммы. Если она большая, то ДП вам не поможет.
Для сверхбольшой размерности у меня есть очень хороший алгоритм (дипломница писала для нашей бухгалтерии, для планирования госзакупок), но программного кода нет, т.к. писала не я. Сразу должна сказать, что алгоритм довольно сложный. В смысле не так просто программируется, как это всё.
Если ДП вам не подойдёт, могу дать описание. Есть и статья, "Информационные технологии", 2019 год, №4 ("Гибридный" алгоритм планирования государственных закупок товарно-материальных ценностей). Там есть пример работы на модельном примере, но подробное описание попросили убрать.

swf
Спасибо за ответ! Да вы правы тут 2 варианта .... в моем случае важно списать больше разного товара максимально приближаясь к этой сумме,при необходимости в дальнейшем можно будет сделать корректировку добавлением проводок списания в ручном режиме для достижения точного соответствия сумме. Насчет суммы нужно списать за 3 года... но в любом случае списывать нужно каждый день, учитывая закупку, возврат товара. Придумал еще разделить товары на группы типа каждодневные товары (хлеб, сыр, масло, колбаса, молоко, алкоголь....и.т.д.), и товары которые продаются в разный сезон в процентном соотнешении с каждодневными вместе в зависимости от времени суток, сезона и времени года... ну как бы модель того что могло бы продаваться в разное время года.

Был бы рад любой помощи особенно знанием .... если есть такой алгоритм буду очень благодарен вам если есть возможность дать полное описание.

Спасибо, всем кто написал и помог ценным советом!

Сообщение отредактировано: test4me - 03.07.21, 08:04

Хорошо, я прикреплю текстовый файл с полным описанием алгоритма (надеюсь, найду на компьютере, вечером после футбола поищу муж через комп футбол смотрит). И тестовый пример работы алгоритма на небольшом наборе данных покажу, чтоб на пальцах объяснить идею. У нас для каждого подразделения набирались большие суммы (несколько миллионов рублей) и количество слагаемых было очень большим (например, один только список канцтоваров для кафедры, каждый канцтовар - отдельный лот), а сумма набиралась очень точно, с отклонением в несколько рублей. То есть этим алгоритмом вы можете сразу набрать всю сумму за три года. А потом эту сумму другим алгоритмом можно задним числом раскидать по дням. Это если задним числом делать.

А если вы каждый день должны списывать небольшую сумму, то можно ДП обойтись. Если стоимости округлить до рубля, то какая будет сумма, столько будет столбцов в табличке. Правда, я ДП реальные задачи не решала, не знаю, какой там максимум количества столбцов. Может, кто-нибудь подскажет.

swf
Спасибо большое как раз то что нужно... да и проводки задним числом нужно провести за 3 года....суммы тоже не маленькие за день..(да придется тем более их умножать на 100 делать целыми) буду ждать ваше сообщение!

Вот ссылка на полный алгоритм
https://disk.yandex.ru/i/bDJwOJj6IHxUoQ

Объяснения после футбола

swf
Спасибо получил...разбираюсь.... тоже после футбола зайду))))

Начнём с конца. Гибридный алгоритм состоит из двух алгоритмов: точного и эвристического. Вначале эвристический набирает сумму, меньшую заданной. Когда остаётся не больше 20 слагаемых, то сумму добирает точный переборный алгоритм с возвратом, для 20 слагаемых он работает мгновенно, за счёт перебора набирает очень точно. Этот точный алгоритм описан и есть мои исходники к нему в этой теме:
http://forum.sources.ru/index.php?showtopi...EC%EC%FB&st=15#
Мой ник там Swetlana, посмотрите мои сообщения.

Что касается вашей реальной задачи. Цены на продукты питания всё время растут. За три прошедших года сразу нельзя сумму набрать, потому что цена на каждый вид продукции (лот) с течением времени менялась. Тут нужно подумать. И нужно знать, как она (цена) менялась. 3 года, пусть это будет n=3*365 дней. Для каждого лота нужно завести строку (массив) длины n и проставить цену. И так по каждому лоту. У вас есть такие данные?

Сообщение отредактировано: swf - 03.07.21, 20:35

swf
Прочел несколько раз пытаюсь осмыслить все в алгоритме... очень интересно... спасибо Светлана по ссылке нашел тему... насчет продуктов да особенно за 2 года выросло очень в разы.... но у меня есть данные закупок уже все с реальными ценами за 3 года и возвраты все которые были, также есть терминальные выплаты + чековые данные только не отдельно чеки а за весь день одной суммой. Вот есть закупки товара + возвраты + сумма с терминалов + чековые суммы за каждый день и это та сумма на которую надо списать... Пока все вроде бы понятно спасибо очень наглядно и подробно все подсказываете... займусь пока все прочитаю по ссылке!

Добавлено 03.07.21, 21:28
swf
Значит как я понял из выше сказанного нужно для начала:
списать сразу за 3 года не получится изза того что операция списания будет зависит от даты закупки и возврата каждого товара и на тотже день надо посчитать чеки + терминал (((
1) на каждый день пересчитать последовательно за все 3 года каждый продукт (ЗАКУПКА-ВОЗВРАТ) получим реальное оставшееся количество и сумму на каждый день на все 3 года...
2) на каждый день пересчитать последоватльно также СУММА ТЕРМИНАЛА + СУММА ЧЕКА
и потом надо уже испоьзовать алгоритм получить на сумму (СУММА ТЕРМИНАЛА + СУММА ЧЕКА) слагаемые сумм как можно большего числа на тот день товаров.... как наберется это сумма узнаем количество уже тех товаров которые спишем и так повторим за оставшиеся дни в течении 3 лет... кажется так... если нет поправьте...

Сообщение отредактировано: test4me - 03.07.21, 21:28

Алгоритм какой-нибудь придумаем)) Надо вначале с реальной задачей разобраться. Я пока не поняла, какие данные у вас есть.
Чековая сумма за день - это суммарная стоимость проданного за день?
Возвраты - это понятно, кто-то вначале купил (возможно, в другой день), а сегодня вернул.
То есть из проданного за 3 года нужно вычесть возвраты за 3 года. Пока вроде понятно.
А что такое сумма терминала?
Данные закупок с реальными ценами - это какие данные? Пример какой-то приведите, чтобы я поняла.

swf
доброго времени суток!
Да все правильно Чековая сумма - сумма за день... так назваемый (Z)... сами чеки за продажу каждого товара и его количества и суммой были утеряны поэтому есть только чековая сумма за каждый день после закрытия дня.
Возвраты в нашем случае - возвраты закупок которые были по какой-либо причине возвращены нами не покупателями!
Терминальная сумма это выписка из банка то что было заплачено по терминалу кредитками безналичным расчетом.
Данными с реальными ценами я называю как раз закупки которые были сделаны и их данные как раз есть все с количеством и ценой что когда закупали какой товар в течении этих 3 лет - поэтому называю реальными))))
По факту скажем на начало 2018 года есть товары: известны остаток, себестоимость и цена.
Берем первый день - есть приход по некоторым товарам тоесть закупка товара а также возможен и возврат по какой либо причине который был еще закуплен нами в 2017 году в конце года. Ну и 3-й компонент это наша реализация,
которую нам надо уже по алгоритму самим решать какой товар реализовать в каком количестве с какой себестоимостью и ценой.
То есть 1-е действие ОСТАТОК КОЛИЧЕСТВО + НОВОЕ КОЛИЧЕСТВО и ОСТАТОК СУММА + НОВАЯ СУММА (Новая закупка, это только в тех товарах у которых на данное число была закупка) МИНУС отсюда если был возврат по этому товару
(ВОЗВРАТ КОЛИЧЕСТВО) и (ВОЗВРАТ СУММА) = (ФАКТ КОЛИЧЕСТВО) и (ФАКТ СУММА) вот это как раз одно слагаемое из таких же товаров, а слагаемых этих должно быть столько сколько товара на этот день где количество товара>0. Что касается суммы к которой нужно подобрать слагаемые это опять же (ЧЕКОВАЯ СУММА - НДС (18%)) + (ТЕРМИНАЛЬНАЯ СУММА - НДС (18%)) на этот же день по этому товару. И так в цикле наверно 3*365 * N(товара)!

Сообщение отредактировано: test4me - 04.07.21, 19:18

Поехали дальше))
1. Терминальная сумма: тут тоже неизвестно, что покупали? Только сумма за день? Или как в чеке список стоимостей товаров, к-ые были оплачены?
2. Закупка - это то, что вы закупаете. Приход товара. И на каждый лот известно количество, себестоимость (это закупочная цена?) и ваша цена (по которой продавали).
3. Возврат - когда закупленный когда-то товар возвращается от вас производителю.
Так?

swf
1. Терминальня сумма просто сумма каждого кто заплатил кредиткой, но банк не учитывает что купили сколько и по какой цене... продавец посчитала сколько за все и провели кредиткой по терминалу она фиксирует это на банковском сервере и списывает сумму у покупателя. То есть чтото купили одно или разного и разного количества всеравно сумму выбивают и платят кредиткой. Вот это единичные проводки каждого покупателя есть за весь период 3 года.
2. Закупка наш приход что мы закупаем чтобы продавать покупателю... известно количество и себестоимость = (закупочная цена), продажной цены нет и количества нет это то что нужно найти чтобы списать, но известна общая наценка 10-12% и еще НДС 18%.
3. да Возврат от нас то что когда то купили иногда возвращаем продавцу это как бы тоже реализация но без наценки.

Добавлено 04.07.21, 20:37
В любом случае ищем слагаемые (сумма товаров количество которых больше 0 в тот день после прибавления закупок если были в этот день и минус если были возвраты в этот день) а ищем в сумме на этот же день (терминальная сумма +
чековая сумма - наценка 10%-12% и минус НДС 18%) как находим подходящие суммы этих продуктов важно знать код этих продуктов чтобы по нему узнать себестоимость ну а дальше просто эту сумму поделив на себестоимость узнаем количество этого товара, который надо списать вместе с суммой и количеством и потом отнимаем от суммы этого товара сумму которую нашли по алгоритму и сохраняем в ОСТАТОК СУММА и также от количества продукта отнимаем количество списываемого товара и сохраняем в ОСТАТОК КОЛИЧЕСТВО и на каждый участвовавший продукт за этот день... ну и все это повторяем на следующий день и так 3года * 365!

Добавлено 04.07.21, 20:41
Думал все разом получится както легче за все 3 года... но в любом случает нужно учитывать остаток товара и его сумму на следующий день (((( усложняется алгоритм да?

Добавлено 04.07.21, 20:49
swf
кажется ошибся с поиском слагаемых не сумму надо искать нам а себестоимость =(номинал) в слагаемое ставить, так как мы сможем регулировать количеством сумму слагаемого так ведь?

Сообщение отредактировано: test4me - 04.07.21, 20:51

Цитата test4me @ 04.07.21, 20:21

swf
2. Закупка наш приход что мы закупаем чтобы продавать покупателю... известно количество и себестоимость = (закупочная цена), продажной цены нет и количества нет это то что нужно найти чтобы списать, но известна общая наценка 10-12% и еще НДС 18%.

О!
То есть задача-то у вас совсем другая, более сложная. У меня известная сумма набиралась известными слагаемыми безо всяких ограничений. Так что мой алгоритм в топку Будем придумывать вам новый алгоритм

Что у нас известно.
1) Известна сумма продаж за 3 года.
2) Известна сумма продаж за каждый день.
3) Известно число лотов (разновидностей товаров, которые закупались в течение 3-х лет).
4) Для каждого лота известно, сколько лотов было закуплено и по какой себестоимости.
Что от нас требуется:
1. Подобрать для каждого лота и количество проданных лотов за 3 года, и продажную цену лота для каждого дня.
2. Раскидать проданные лоты по дням.
При ограничениях:
1. Суммарная стоимость всех проданных лотов должна равняться (быть близкой) сумме продаж за 3 года.
2. Суммарная стоимость всех лотов, проданных в один день должна равняться (быть близкой) сумме продаж за этот день.
3. Подобранная стоимость лота для каждого дня должна быть примерно равна себестоимость лота для этого дня + наценка и НДС.
4. Подобранное количество штук в течение дня для некоторых видов лотов должны быть всегда больше некоторого числа. Смысл: каждый день продаем некоторое количество хлеба-молока, там не должен быть ноль.
Так?

Добавлено 04.07.21, 21:01
Ещё одно ограничение забыла!
Для каждого лота и для каждого дня известно, сколько штук было суммарно закуплено к этому дню. То есть мы не можем продать к этому дню суммарно больше штук данного лота, чем было закуплено.

swf
Да уж сначала думал рсплюнуть просто((( но задача оказалось монстром какимто но думаю разрешима все же!!!
1)

Цитата

Известна сумма продаж за 3 года.

Тут мне кажется уже эта сумма не так важна, так как всеравно надо будет перебирать с первого дня последовательно до последнего 3*365!
2)

Цитата

Известна сумма продаж за каждый день.

ДА
3)

Цитата

Известно число лотов (разновидностей товаров, которые закупались в течение 3-х лет).

ДА, хотя опять же изза того что будем последовательно перебирать все думаю нам интересно число лотов в день если они были в этот день для факта чтобы себестоимость была правильная
4)

Цитата

Для каждого лота известно, сколько лотов было закуплено и по какой себестоимости.

ДА

Что от нас требуется:
1. ДА
2. ДА
3. ДА
4. ДА

Цитата

Ещё одно ограничение забыла!
Для каждого лота и для каждого дня известно, сколько штук было суммарно закуплено к этому дню. То есть мы не можем продать к этому дню суммарно больше штук данного лота, чем было закуплено.

всегда есть остаток или его нет... на 2018 год есть товары у которых есть 0 статки и остатки больше 0. В первый же день проверяем по всем продуктам были ли ЗАКУПКИ... если есть закупка даже если у него остаток был 0 то + к нему СУММА ЗАКУПКИ и КОЛИЧЕСТВО ЗАКУПКИ, если не нулевой остаток также... ОСТАТОК СУММА + СУММА ЗАКУПКИ и ОСТАТОК КОЛИЧЕСТВО + КОЛИЧЕСТВО ЗАКУПКА, если в этот же день по этому товару есть ВОЗВРАТ то ОСТАТОК СУММА - СУММА ВОЗВРАТ... ОСТАТОК КОЛИЧЕСТВО - КОЛИЧЕСТВО ВОЗВРАТ таким образом получим на это число ФАКТ СУММА и ФАКТ КОЛИЧЕСТВО данного товара... поделив ФАКТ СУММА/ФАКТ КЩЛИЧЕСТВО = СЕБЕСТОИМОСТЬ то что ищем...Но неможем продать больше ФАКТ КОЛИЧЕСТВО конечно!

Сообщение отредактировано: test4me - 04.07.21, 21:30

Чёто уже не очень соображаю с этими возвратами... Правда, у меня почти 3 ночи. Завтра на свежую голову посмотрю.

Как, кстати, мы можем подбирать цены? Можем, например, каждый день немножко менять цену на товар?
Похоже, цены округлять до рубля нельзя, придётся оперировать копейками. Ну тут ДП можно сказать "прощай!"

Первый подход, самый очевидный. Средние нужно посчитать по каждому лоту и за каждый год.
Знаем, сколько штук было продано за один год (закупка - остаток - возврат, так?) Делим на количество дней - среднее количество штук данного лота, продаваемое за один день. И так по каждому лоту.
Зная эти средние, из них по каждому дню будем формировать первоначальное решение.
Первоначальное решение будем доводить до нужной суммы, то ли добавлять чего-то, то ли убавлять чего-то. Ну тут нужно думать.

Попробую проще смоделировать данные:
1-й день
_______________________________________________________________________________________________________
Продукт | Остаток на 1-й день | Себестоимость | Закупки на 1-й день | Возврат на 1-й день | Чековая сумма на 1й день =320 Терминальная сумма на 1-й день = 176
__________|_________________________|________________|_______________________|_________________________|
| Кол-во | Сумма | Цена | Кол-во | Сумма | Кол-во |
__________|____________|____________|________________|____________|__________|_________________________|
ПР1 10 25 2,5 0 0 2
________________________________________________________________________________________________________
ПР2 8 16 2 10 30 0
________________________________________________________________________________________________________
ПР3 0 0 0 15 35 0
________________________________________________________________________________________________________
ПР4 20 200 10 0 0 5
________________________________________________________________________________________________________
ПР5 0 0 0 20 500 0
________________________________________________________________________________________________________

ПР1 ФАКТ СУММА = ОСТАТОК СУММА + ЗАКУПКА СУММА - ВОЗВРАТ СУММА = 25 + 0 - 2*2,5 = 25 -5 = 20
ФАКТ КОЛ-ВО= ОСТАТОК КОЛ-ВО + ЗАКУПКА КОЛ-ВО - ВОЗВРАТ КОЛВО = 10 + 0 - 2 = 10 - 2 = 8
ФАКТ СЕБЕСТОИМОСТЬ = ФАКТ СУММА / ФАКТ КОЛ-ВО = 20/8=2,5

ПР2 ФАКТ СУММА = ОСТАТОК СУММА + ЗАКУПКА СУММА - ВОЗВРАТ СУММА = 16 + 30 - 0 = 16 + 30 = 36
ФАКТ КОЛ-ВО= ОСТАТОК КОЛ-ВО + ЗАКУПКА КОЛ-ВО - ВОЗВРАТ КОЛВО = 8 + 10 - 0 = 8 + 10 = 18
ФАКТ СЕБЕСТОИМОСТЬ = ФАКТ СУММА / ФАКТ КОЛ-ВО = 36/18=2

ПР3 ФАКТ СУММА = ОСТАТОК СУММА + ЗАКУПКА СУММА - ВОЗВРАТ СУММА = 0 + 35 - 0 = 35
ФАКТ КОЛ-ВО= ОСТАТОК КОЛ-ВО + ЗАКУПКА КОЛ-ВО - ВОЗВРАТ КОЛВО = 0 + 15 - 0 = 15
ФАКТ СЕБЕСТОИМОСТЬ = ФАКТ СУММА / ФАКТ КОЛ-ВО = 35/15=2,33

ПР4 ФАКТ СУММА = ОСТАТОК СУММА + ЗАКУПКА СУММА - ВОЗВРАТ СУММА = 200 + 0 - 5*10 = 200 - 50 = 150
ФАКТ КОЛ-ВО= ОСТАТОК КОЛ-ВО + ЗАКУПКА КОЛ-ВО - ВОЗВРАТ КОЛВО = 20 + 0 - 5 = 20 - 5 = 15
ФАКТ СЕБЕСТОИМОСТЬ = ФАКТ СУММА / ФАКТ КОЛ-ВО = 150/15=10

ПР5 ФАКТ СУММА = ОСТАТОК СУММА + ЗАКУПКА СУММА - ВОЗВРАТ СУММА = 0 + 500 - 0 = 500
ФАКТ КОЛ-ВО= ОСТАТОК КОЛ-ВО + ЗАКУПКА КОЛ-ВО - ВОЗВРАТ КОЛВО = 0 + 20 - 0 = 20
ФАКТ СЕБЕСТОИМОСТЬ = ФАКТ СУММА / ФАКТ КОЛ-ВО = 500/20=25

Сумма к которому будем приближаться в 1-й день:
СУММА = (ЧЕКОВАЯ СУММА - НАЦЕНКА - НДС)+(ТЕРМИНАЛЬНАЯ СУММА - НАЦЕНКА - НДС) или (ЧЕКОВАЯ СУММА + ТЕРМИНАЛЬНАЯ СУММА)- (НАЦЕНКА + НДС)
=(320+176)*(1-(0,1+0,18))=496*(1-0,28)=496*0,72=357,12

ИЩЕМ {25, 10, 2.5, 2.33, 2} в СУММЕ 357,12

Спокойной ночи уже поздно! Спасибо

Сообщение отредактировано: test4me - 04.07.21, 22:26

Подождите, подождите.
Так вы на каждый день знаете, сколько штук каждого товара было к этому дню закуплено и сколько осталось (остаток)?
Тогда вы на каждый день знаете, сколько штук этого товара было продано, не знаете только цену.

swf
Доброго дня!

Цитата

Как, кстати, мы можем подбирать цены? Можем, например, каждый день немножко менять цену на товар?

До просто там все... мы должны в слагаемые этого дня поставить себестоимости продуктов у которых количество >0

Цитата

Первый подход, самый очевидный. Средние нужно посчитать по каждому лоту и за каждый год.

Мне кажется на год и даже на месяц не получится брать.... так как остаток который будет менятся от того какая себестоимость (Номинал монеты) будет менятся количество продукта по этой себестоимости (количество монет этого номинала) поэтому от каждого дня зависит количество этого продукта который мы сможем использовать на следущей итерации 2-го дня итд... если количество этго товара уже 0 то он просто не будет в следующей итерации слагаемых.

Цитата

Знаем, сколько штук было продано за один год (закупка - остаток - возврат, так?)

Закупка это приход нового количества уже товара который имеетс у нас, возможно по другой цене изза чего поменяется только себестоимость может подорожать, но может в какое то время и снизится но редко или вообще это может быть совсем новый товар которого до этого не было еще. И раз Закупка это (плюс) к ОСТАТКУ а не отнимать из закупки остаток...тоесть ОСТАТОК это часть продутка в количестве которая осталась после вчерашней продажи... и к нему прибавим если будет зАКУПКА и отнимем если есть ВОЗВРАТ.

Добавлено 05.07.21, 07:49

Цитата

Подождите, подождите.
Так вы на каждый день знаете, сколько штук каждого товара было к этому дню закуплено и сколько осталось (остаток)?
Тогда вы на каждый день знаете, сколько штук этого товара было продано, не знаете только цену.

ДА так как это прошлое же 2018-2020 годы я знаю остаток каждого товара на начало 2018 года и знаю точно что было закуплено и что возвращено но незнаю что было продано в количестве то что нужно списать а знаю только сумму которая известна из ЧЕКОВОЙ СУММЫ + ТЕРМИНАЛ - НАЦЕНКА - НДС. Мне нужно узнать количество товара но подобрать количество нужно по сумме.

Привет))
Ничего не поняла из вашего объяснения Главный вопрос: за какой срок мы знаем фактическое количество проданного товара: за год, за месяц или как-то иначе.
Вечером вернусь, буду разбираться с исходными данными.
И, пожалуйста, оформите таблички как положено (в форме ответа есть тэги для табличек).

swf

Цитата

Похоже, цены округлять до рубля нельзя, придётся оперировать копейками. Ну тут ДП можно сказать "прощай!"

Думаю каждый отдельный продукт который продается в день не выйдет границу цены слагаемого больше чем 100000!!! Так как там будут и копейки незнаю что лучше для точности результата будет отбросить их или умножить на 100?

Добавлено 05.07.21, 08:11

Цитата

И, пожалуйста, оформите таблички как положено (в форме ответа есть тэги для табличек).

Да извините делал на скорую руку когда оформлял было нормально в редакторе а потом как отправил все съехало нетуда ((( все исправлю к вечеру и еще на примерах попытаюсь объяснить..
Спасибо за ваше время! Удачного дня! С уважением!

swf

Цитата

за какой срок мы знаем фактическое количество проданного товара: за год, за месяц или как-то иначе.

Фактическое количество проданного уже товара нам не известно так как чеки где были данные с кодом продукции (названием) количеством, продажной ценой за единицу, общей суммой были утеряны!
Нам известна лиц общая сумма всех этих чеков которые были выбиты за день (имею ввиду за "день" так как эта инфа имеется на каждый день из этих ТРЕХ лет). Нам по этой общей сумме надо узнать какие товары могли бы быть проданны на эту сумму и в каком количестве.
Представьте допустим было всего за день 1300 покупателя. Чтобы легче было представить напишу маленькими цифрами.

1-й Покупатель купил разные товары (скажем ПР1, ПР2, ПР3)
ПР1 в количестве 4 шт по цене 2 за штуку,
ПР2- 5 шт по цене 3 за штуку ,
ПР3-1шт по цене 5 за шт:

ПР1=4*2=8,
ПР2=5*3=15,
ПР3=1*5=5
==========================
Всего на сумму 8+15+5=28 Это лишь 1 покупатель...таких за день может быть от 1 до 2000...в нашем случае мы условились что было 1300 покупателя.


Отсюда имеем чек который мы потеряли и где все видно что как почем и сколько... надо было сразу списать это количество товаров так как мы знаем что продали
ПР1=4шт,
ПР2=5шт,
ПР3=1шт
и было бы все ХОРОШО... но неважно почему и зачем и как так получилось... эти товары не списаны и их надо списать теперь задним числом, НО так как мы уже потеряли эти чеки у нас нет информации какое количество какого продукта
продано в конкретный день есть только СУММА которая ОБЩАЯ ЗА ЦЕЛЫЙ ДЕНЬ и там все чеки каждого покупателя за этот день просуммированы в этой сумме. Мы рассмотрели 1 покупателя что он купил так ведь, так вот имеющаяся СУММА у нас на руках это сумма например 1300 покупателей, и допустим эта сумма за день составляет 356708.

Так вот моя задача заключается чтобы узнать какие продукты могли бы быть проданы в каком количестве на сумму не выше но близкую к 356708.

Добавлено 05.07.21, 10:43
swf

Какие мои действия как узнать?

Я знаю за день мой начальный остаток какжого товара, Допустим товаров всего 10 штук, знаю его себестоимость. Знаю была ли ЗАКУПКА если да то что закупили и в каком количестве, тоесть знаю себестоимость, Знаю был ли ВОЗВРАТ и если был какое количество возвратили, возвращаем всегда также по себестоимости как и купили его. Вычисляю на каждый продукт из 10 его ФАКТИЧЕСКУЮ СЕБЕСТОИМОСТЬ учитывая ОСТАТОК, ЗАКУПКУ и ВОЗВРАТ.

Что получили?

получили себестоимости 10 товаров за день. Допустим условно {10.56, 8.36, 11.78, 45.40, 4.28, 7.74, 3.89, 5.09, 15.42, 18.73} и у нас сумма 356708, тепрь алгоритм мне нужен помочь найти оптимальное решение приблизившись к этой сумме слагаемыми из себестоимостей (себестоимость это цена 1шт товара) увеличивая сумму слагаемого умножая на себестоимость и таким образом приближаться к сумме 356708. По ходу надо учитывать код товара продукта тесть у нас должен быть отдельно или вместе с себестоимостями еще и код продукта, например {101, 102, 103, 104, 105, 106, 107, 108, 109, 110}.

Зачем это нужно?

допустим мы получили после работы алгоритма такие слагаемые сумм {22326, 12708, 45200, 15763, 78800, 23500, 15300, 24202, 50235, 88674} все по кодам я уже могу знать что товар 101 например был за этот день продан на 22326 и его количество просто узнать эту сумму делю на его себестоимость тоесть 22326/10.56 =2114.2 ну когда алгоритм сработает на самом деле получим уже целые числа.... это значит нам надо в этотт день списать продукт 101 в количестве 2114 и так со всеми продуктами в этом списке...

Что дальше?

Это был 1-й день из 3*356 дней... допустим остаток товара на 1-й день был 3200 шт это мы узнали когда узнали ФАКТИЧЕСКУЮ СТОИМОСТЬ и ФАКТИЧЕСКОЕ КОЛИЧЕСТВО что дало нам ФАКТИЧЕСКУЮ СЕБЕСТОИМОСТЬ...
тепрь для 2-го дня делаем остатки этого товара 3200-2114=1086шт Теперь у нас для 2-го дня готов по продукту 101 ОСТАТОК КОЛИЧЕСТВО=1086, ОСТАТОК СУММА=ФАКТИЧЕСКАЯ СЕБЕСТОИМОСТЬ * ОСТАТОК КОЛИЧЕСТВО=10.56*1086=11 468.16
И так по всем продуктам в нашем случае 10 было их. Все эта итерация закончена теперь на 2-й день... и так пока не пройдем 3*356 дней... незнаю насколько все доступно объяснил... если не понятно было не поленюсь еще раз!!!

Сообщение отредактировано: test4me - 05.07.21, 10:43

Цитата test4me @ 05.07.21, 09:54

swf

Цитата

за какой срок мы знаем фактическое количество проданного товара: за год, за месяц или как-то иначе.

Фактическое количество проданного уже товара нам не известно так как чеки где были данные с кодом продукции (названием) количеством, продажной ценой за единицу, общей суммой были утеряны!
Нам известна лиц общая сумма всех этих чеков которые были выбиты за день (имею ввиду за "день" так как эта инфа имеется на каждый день из этих ТРЕХ лет). Нам по этой общей сумме надо узнать какие товары могли бы быть проданны на эту сумму и в каком количестве.
Представьте допустим было всего за день 1300 покупателя. Чтобы легче было представить напишу маленькими цифрами.

1-й Покупатель купил разные товары (скажем ПР1, ПР2, ПР3)
ПР1 в количестве 4 шт по цене 2 за штуку,
ПР2- 5 шт по цене 3 за штуку ,
ПР3-1шт по цене 5 за шт:

ПР1=4*2=8,
ПР2=5*3=15,
ПР3=1*5=5
==========================
Всего на сумму 8+15+5=28 Это лишь 1 покупатель...таких за день может быть от 1 до 2000...в нашем случае мы условились что было 1300 покупателя.


Отсюда имеем чек который мы потеряли и где все видно что как почем и сколько... надо было сразу списать это количество товаров так как мы знаем что продали
ПР1=4шт,
ПР2=5шт,
ПР3=1шт
и было бы все ХОРОШО... но неважно почему и зачем и как так получилось... эти товары не списаны и их надо списать теперь задним числом, НО так как мы уже потеряли эти чеки у нас нет информации какое количество какого продукта
продано в конкретный день есть только СУММА которая ОБЩАЯ ЗА ЦЕЛЫЙ ДЕНЬ и там все чеки каждого покупателя за этот день просуммированы в этой сумме. Мы рассмотрели 1 покупателя что он купил так ведь, так вот имеющаяся СУММА у нас на руках это сумма например 1300 покупателей, и допустим эта сумма за день составляет 356708.

Так вот моя задача заключается чтобы узнать какие продукты могли бы быть проданы в каком количестве на сумму не выше но близкую к 356708.

С этим я всё поняла. Есть
1) дневная сумма продаж по всем товарам;
2) есть себестоимость товаров, а по себестоимости делаем примерную продажную цену, которую можно немножко корректировать.
Далее, как вы сказали, нужно набрать продуктов на дневную сумму продаж.

Но не понимаю пока, как выставлять ограничения.
Мы знаем сколько было закуплено продуктов, сколько было сделано возвратов, то есть знаем сколько было продано по факту. Я спрашиваю: за какой период мы это знаем? За год, за месяц? Или за 3 года сразу?
Вот эти таинственные остатки, это что? Они на каждый день известны? Или раз в год мы узнаём, сколько осталось товара непроданным?
Ну вот по-простому скажу.
Мы придумаем на год, сколько товаров было продано в каждый день, сумма товаров сойдётся, скажем, с годовой суммой закупок.
Но нас поймают по этим остаткам: вы за месяц продали больше товара, чем было закуплено.
Или вы за месяц продали товара столько, сколько было закуплено, а у вас в конце месяц есть ненулевой остаток по этому товару, вы столько не могли продать.
Откуда брать ограничения на количества товара и за какой период?

swf

Цитата

Мы знаем сколько было закуплено продуктов, сколько было сделано возвратов, то есть знаем сколько было продано по факту.

Мы знаем сколько закупили и вернули и знаем только СУММУ продажи но никак количество...как раз задача найти какие продукты войдут в эти продажи своими себестоимосями * на количество.
Ну вот прсотой пример мы знаем что я сегодня купил 3 продукта и за все заплатил 3000 руб но незнаю что купил ))) я могу кпить молоко, хлеб, творог на эту сумму, а могу и пива, колбасу, кетчупа ))) сумма в обеих случаях одинаковая затрачена но количество разное так ведь? мне не важно что я купил на 3000 руб...главное любые продукты чтобы приблизились своей сеестоимостью * количество этого продукта.

Цитата

Я спрашиваю: за какой период мы это знаем? За год, за месяц? Или за 3 года сразу?

Меня устроило бы сразу на 3 года все сразу но ведь не получится количество меняется в зависимости какое количество найдем по алгоритму и на 2-й день надо пересчитать как в первый все заново как в 1-й день

Цитата

Вот эти таинственные остатки, это что?

Представь что у тебя в кошелке есть 1000 руб... сейчас начался новый день это остаток на начало дня... вернули долг 5000 руб сегодня.... это ЗАКУПКА у тебя вместе с ОСТАТКОМ + ЗАКУПКА = 6000 руб, но тебе надо вернуть свой долг 2000 руб подруге... это ВОЗВРАТ -2000...Итого у тебя ОСТАТОК+ЗАКУПКА-ВОЗВРАТ=1000+5000-2000=4000 руб и если никаких больше трат и возвратов нет на этот день то это становится ОСТАТКОМ на завтра...

Добавлено 05.07.21, 19:56
swf
Просто товары измеряются в 2х измерениях Финансово и Количественно... у нас есть закупки как финансово так и количественно и возвраты такж... но продажи есть только финансово нет количественого... чтобы списать товар который мы закпули нам надо знать количество и какого товара.... как выше сказал мне всеравно какой это товар будет лишь бы приблизился к сумме а количество определится...

Цитата test4me @ 05.07.21, 19:46

Просто товары измеряются в 2х измерениях Финансово и Количественно... у нас есть закупки как финансово так и количественно и возвраты такж... но продажи есть только финансово нет количественого... чтобы списать товар который мы закпули нам надо знать количество и какого товара.... как выше сказал мне всеравно какой это товар будет лишь бы приблизился к сумме а количество определится...

Закупки у нас есть количественно. Отсюда получаем ограничения.

Мы знаем, что 1 января мы закупили 100 штук ПР1.
Мы знаем, что 10 января закупили 50 штук ПР1.
Мы знаем, что 14 января вернули 50 штук ПР1.
Мы знаем, что 20 января мы снова закупили 50 штук ПР1.
Значит, с 1 по 19 января мы могли продать не более 100 штук ПР1. А если мы за этот период (с 1 по 19 января) продадим 150 штук ПР1, то нас поймают за руку: продали товара больше, чем было закуплено.
То есть в период с 1 по 19 января мы можем продать не более 100 штук ПР1.
А в период с 1 по 31 января можем продать не более 150 штук ПР1.
Это ограничения только исходя из данных закупок и возратов. А ещё у нас есть остатки.
Ну не могу понять с остатками.

Остаток - это что?
Сумма в рублях по всем непроданным товарам?
Или сумма в рублях отдельно по каждому товару?
Или это и сумма в рублях, и количество непроданных штук по каждому товару?
И эти остатки мы на каждый день знаем или только по праздникам?

Цитата

Остаток - это что?

Остаток это просто оставшийся непроданным товар вчерашний... он может быть и 0 если нет этого товара... или например мы вчера открыли магазин у нас пока нет ничего значит остаток на начало дня у нас 0 а если мы открылись позавчера и вчера закупились вернули возврат и продали то что осталось после вчерашнего после всего... это остаток на начало дня сегодня скажем 2 товара ПР1 в количестве 15шт которые стоят 3000руб и ПР2 20шт который стоят 5000руб

Цитата

Или это и сумма в рублях, и количество непроданных штук по каждому товару?

ЭТО ОНО))))

Добавлено 05.07.21, 20:20
так как они взаимосвязаны количество и сумма определенного товара, а сумма/количество дает цену этого товара - себестоимость вот ее нужно в слагаемое чтобы приблизится к искомой сумме с другими продуктами

Добавлено 05.07.21, 20:25

Сообщение отредактировано: test4me - 10.07.21, 05:38

Остаток по каждому товару мы знаем каждый день в штуках. И мы знаем, сколько мы закупали в штуках и сколько возвращали в штуках.
Значит, по сегодняшнему остатку мы можем сказать, сколько мы вчера продали.
Ну смотрите.
Мы знаем, что 1 января мы закупили 100 штук ПР1.
Утро 2 января. Остаток ПР1 - 98 штук. Значит, 1 января продали 2 штуки.
Утро 3 января. Остаток ПР1 - 90 штук. Значит, 2 января продали 98-90 = 8 штук.
Утро 4 января. Остаток ПР1 - 0. Значит, 3 января продали 90 штук.
А в чём тогда проблема?

swf

Цитата

Остаток по каждому товару мы знаем каждый день в штуках. И мы знаем, сколько мы закупали в штуках и сколько возвращали в штуках.
Значит, по сегодняшнему остатку мы можем сказать, сколько мы вчера продали.
Ну смотрите.
Мы знаем, что 1 января мы закупили 100 штук ПР1.
Утро 2 января. Остаток ПР1 - 98 штук. Значит, 1 января продали 2 штуки.
Утро 3 января. Остаток ПР1 - 90 штук. Значит, 2 января продали 98-90 = 8 штук.
Утро 4 января. Остаток ПР1 - 0. Значит, 3 января продали 90 штук.
А в чём тогда проблема?

да все было бы просто если бы так.... на 1 января все нормально закупили и вернули но не продали штучно....только финансово... а нам надо это в штуках))))

Ну вы же мне сами написали, что остаток - это и сумма, и количество штук. И по каждому виду товара. И каждый день с утра мы знаем остаток.
Значит, проданное (в штуках вчера) = остаток (в штуках) вчера - остаток (в штуках) сегодня утром .

Добавлено 05.07.21, 22:20
Это продали вы только финансово, а остаток у вас известен только финансово или в штуках?

Цитата

Это продали вы только финансово, а остаток у вас известен только финансово или в штуках?

давайте не будем считать остаток и 2018 год 1 января будем считать что у нас ничего нет... товар я уже говорил всегда в 2х измерениях количественно учитывается и денежно...тоесть абсолютно любая операция закупка возврат продажв это все в деньгах и количественно так ведь? если у вас было закуплено 10 потом вы вернули 2 осталось 10-2=8 и если не было других операций это остаток и он тоже в 2х измерениях в количественном и денежном...
тоесть если мы купили за 2000 руб 20 штук чегото и вернули 5 штук у нас в наличии если штучно сколько? 20-5=15 штук...а в денежном будет столько: 2000-2000/20*5=2000-500=1500руб. Представь что не 1 товар тут а 10 разных товаров и мы знаем только общую сумму продажи и никак незнаем что продали как определить из суммы 35000 какой товар и сколько продали?

Добавлено 05.07.21, 22:42
swf
Совсем замучил с остатками вас))) уже поздно отдыхайте! Спойоной ночи! Давайте продолжим завтра! Спасибо за потраченное время и желание помочь!

Вы бы привели набор исходных данных за неделю хотя бы, может тогда понятней бы стало.

swf
Доброго дня!

Цитата

Ну вы же мне сами написали, что остаток - это и сумма, и количество штук. И по каждому виду товара. И каждый день с утра мы знаем остаток.
Значит, проданное (в штуках вчера) = остаток (в штуках) вчера - остаток (в штуках) сегодня утром .

Хочу сказать чтобы остаток легче понять что такое... нужно принять что каждый день имеет начало периода когда начинается процесс работы (торговли) и конец когда закрываемся. Так вот Допустим что работаем с 8 утра до 20 вечера.
Значит в этот период ОСТАТОК на начало дня это все товары которые остались после вчерашнего, тоесть мы вчера закупили если была закупка, возвратили если был возврат, продали... и на конец дня у нас осталось какое-то количество товаров, которое также может быть нулевым. ЭТО теперь ОСТАТОК на начало дня. Теперь все повторяется закупка, возврат и реализация... и остается ОСТАТОК на конец дня, кторый завтра с утра будет ОСТАТОК на начало дня... у нас есть данные на каждый день в течении 3 лет начальный остаток который был 31.12.2017 значит это точка отсчета... как мы откроемся у нас уже есть по большинству товаров количество больше нуля, но некоотрые могут быть и нулевыми, также есть данные закупки и возврата если они есть... есть продажа (реализация товара) но только финансовая часть...нам надо как раз это найти ну и ОСТАТОК уже сам вычислится на конец дня, который будет утром следующего дня опять ОСТАТКОМ на начало дня.

Готовлю исходные данные за месяц в excel пойдет?

Сообщение отредактировано: test4me - 07.07.21, 06:14

swf
Исходные данные в Excel
Напиши если скачалось...

Цитата

нам надо как раз это найти

забыл дописать количество надо найти есть только финансовая часть

Сообщение отредактировано: test4me - 07.07.21, 10:59

Подождите, не готовьте за месяц.
Возьмите ровно один товар и покажите за два соседних дня данные по этому товару.
Где финансы - пишите руб, где количества - пишите шт.
Лучше воспользоваться табличкой

1 день	... (руб)	... (шт.)
2 день	... (руб.)	... (шт.)

Если не получается с табличкой, то сделайте в ворде табличку и прикрепите текст. файл к посту.

Добавлено 07.07.21, 10:58

Цитата test4me @ 07.07.21, 10:53

swf
Исходные данные в Excel
Напиши если скачалось...

Скачала

Да хорошо сделаю на примере того что выслал

Разбираюсь со штуками, там полштуки не продашь. С кг будет проще.
Ещё есть блоки. Для блока бы надо знать сколько там внутри. Если неизвестно, будем, считать, что 10 штук.
-----------------------------------------------------------------------
Вот, например, товар №26 002870000055
Остаток известен только на 1 октября 2895 штук на 201155,78 рубликов.
В октябре его больше не закупали и не возвращали.
Вопрос.
Когда снова увидим остаток этого товара? В данных на 1 ноября?

Добавлено 07.07.21, 12:00
Вопрос относительно возвратов
Товар № 603 002870002230 остаток на 1 октября 349 штук
Потом в октябре множество возвратов этого товара. Вначале возвращаем целыми числами. А потом возвраты дробные: 0,9; 0,75 и т. д.

Цитата

Вот, например, товар №26 002870000055
Остаток известен только на 1 октября 2895 штук на 201155,78 рубликов.
В октябре его больше не закупали и не возвращали.
Вопрос.
Когда снова увидим остаток этого товара? В данных на 1 ноября?

Да я взял октябрь с 1-го по 31... думаю месяц не имеет на наданный момоент, если нет товара по этому коду значит он 0 я просто отфильтровал.... но если купят он появится...

Цитата

Вопрос относительно возвратов
Товар № 603 002870002230 остаток на 1 октября 349 штук
Потом в октябре множество возвратов этого товара. Вначале возвращаем целыми числами. А потом возвраты дробные: 0,9; 0,75 и т. д.

извини мой косяк когда копировал тупо код одного товара скопировалс...замени пожалуста там на следующее весь столбец:
002870000074
002870000074
............
002870006804

Сообщение отредактировано: test4me - 07.07.21, 14:19

Понятно с возвратами.
Непонятно с остатками. В таблице остатки по каждому товару даны на 1 октября.
Что я хочу увидеть. Возьмите один товар, который штуками меряется. И покажите остатки по нему за какой-то период времени. За 1 октября, за 2 октября и т.д.

Цитата

Возьмите один товар, который штуками меряется. И покажите остатки по нему за какой-то период времени. За 1 октября, за 2 октября и т.д.

остаток 1-го дня на конец дня будет известен только после того как мы из алгоритма получим сумму этого продутка в слагаемых а значит зная эту сумму и себестоимость - узнаем количество продажи в этот день....следовательно ОСТАТОК на конец дня = ОСТАТОК НА НАЧАЛО ДНЯ + ЗАКУПКА - ВОЗВРАТ - ПРОДАЖА (то что узнали количество из алгоритма). Это и будет остаток на конец 1-го дня по этому продукту... ну а на 2-й день это уже остаток на начало дня...итд...тоесть динамически

Добавлено 07.07.21, 13:06
тоесть пока не узнаем из алгоритма сумму нет смысла говорить о следующем дне для этого продукта

Сообщение отредактировано: test4me - 07.07.21, 13:06

Номер дня	Дата	Товар	Остаток в начале на эту дату (руб)	Остаток в начале на эту дату (шт)	Закупка (руб)	Закупка (шт)	Возврат (руб)	Возврат (шт)	Продажа (руб)	Продажа (шт)	Остаток на конец этого дня (руб)	Остаток на конец этого дня (шт)
1-й	01.10.2018	002870002230	93169.19	349.00	1602.66	6	0	0	XXX	BBB	CCC	DDD
1-й	01.10.2018	002870003921	5625.13	32	182.02	1	AAA	1	XXX	BBB	CCC	DDD
1-й	01.10.2018	002870004755	8816.37	16	551.44	1	0	0	XXX	BBB	CCC	DDD
1-й	01.10.2018	002870003456	30869.79	205	458.21	3	AAA	3	XXX	BBB	CCC	DDD

СУММА ПРОДАЖ на этот день = 363117.8


Добавлено 07.07.21, 13:31
замучился в эту таблицу все это вписывать.... ужасно неудобно((( ну ладно вроде бы все правильно впихнул...сейчас попробую объяснить что буквами обозначил и как это определить исходя из этой таблицы

Добавлено 07.07.21, 14:16
1) наша задача заключается найти в столбце Продажа (руб) все XXX (это неизвестные слагаемые, которые должен выдать алгоритм) для общей суммы СУММА ПРОДАЖ на этот день.
Чтобы это сделать нам нужны СЕБЕСТОИМОСТИ этих продуктов:
сначала для одного продукта делаем, как пример но нужно для всех, складываю Остаток начала дня с закупкой в рублях сначало 93169.19+1602.66=94771.85, а теперь количество 349.00+6=355, теперь надо узнать себестоимость продукта (цена товара за 1 шт) 94771.85/355=266.96, так как у нас возврата нет тут это конечная СЕБЕСТОИМОСТЬ (то что положим как одно из слагаемых для поиска в алгоритме).
Сделаем тоже самое со 2-м продуктом у него есть и возврат... 5625.13+182.02=5807.15, 32+1=33, 5807.15/33=175.97 это себестоимость 2-го товара, но у нас есть еще и возврат (будем умножать себестоимость на количество возврата и получим какую сумму надо отнять) возврат 1 шт, значит ААА=175.97*1=175.97 и это отнимаем из 5807.15-175.97=5631.18 и колчество 33-1=32, и еще раз определяем из получивших данных себестоимость 5631.18/32= 175.97 это конечная СЕБЕСТОИМОСТЬ для 2-го товара...и ее тоже в слагаемы для поиска в алгоритм.

2) Допустим что алгоритм выдал нам слагаемые {55200, 88600, 102000, 117200}. Это значит мы нашли приближения которые самые близко подошли к нужной сумме продаж 363117.8 значит подставляем эти суммы в таблицу вместо ХХХ будем узнавать сколько это в штуках. А в штуках для 1-го это будет надо эту сумму разделить на себестоимость 55200/266.96=206 штук... ну а теперь мы узнаем ОСТАТОК на конец дня.. ССС=94771.85-55200=39571.85, DDD=355-206=149.. ну все тоже самое с другими продуктами...

Сообщение отредактировано: test4me - 07.07.21, 16:40

Надеюсь смог объяснить... какой алгоритм использовать теперь???

Хорошо, завтра постараюсь разобраться с остатками.

Что касается алгоритма. Мы здесь набираем не одну сумму, а одновременно несколько, т.к. общая дневная сумма раскидывается по разным продуктам.
Теперь, если не принимать во внимания эти остатки, то похожий алгоритм и готовая программа уже есть.
Задача
Что там делалось (насколько я помню). Там происходило равномерное распределение работ по n бригадам, чтоб все были загружены одинаково.
Что для вашей задачи будет.
Общая дневная сумма будет раскидываться на n сумм, причём для каждой частичной i-той суммы будут даны верхняя и нижняя границы, т.е. сумма должна быть в этих границах.
Что пока непонятно:
1) как выбрать из всех продуктов эти n продуктов;
2) как выбрать границы, в которые будет заключена каждая частичная сумма.
Видимо, информация о закупках, возвратах и остатках будет определять и выбор продуктов, и границы частичных сумм.

Цитата

Что касается алгоритма. Мы здесь набираем не одну сумму, а одновременно несколько, т.к. общая дневная сумма раскидывается по разным продуктам.

Да думаю как раз что надо... тогда завтра подробнее рассморим если можно...

Цитата

1) как выбрать из всех продуктов эти n продуктов;

Мне нужно охватить как можно больше продуктов из всех возможных... тоесть если возможно и позволяет сумма хоть по одной штуке товара на первой итерации из всех товаров...и после этого если еще остается сумма еще раз как можно больше разных товаров охватить (в идеале бы все если позволяет сумма этих товаров) и конечно же нужно как можно ближе подойти к общей сумме....

Цитата

2) как выбрать границы, в которые будет заключена каждая частичная сумма.

мне не понятно про границы пока.

Сообщение отредактировано: test4me - 07.07.21, 18:29

Цитата test4me @ 07.07.21, 13:04

нет смысла говорить о следующем дне для этого продукта

Ну нет смысла - и не будем. Нам же легче.

Возьмём данные, скажем, за самый первый месяц. Зафиксируем один продукт.
Мы знаем, сколько было закуплено в этом месяце и сколько возвращено. Будем считать, что за первый месяц мы продали всё: все закупки - все возвраты. То есть никакого остатка на начало след. месяца не было. Во всяком случае, из ваших данных этого не видно.
1. Весь товар, закупленный и не возвращённый в этом месяце, делим на число дней в месяце, округляем до целого. Делаем во все дни одинаково, в последний день так, чтобы набрать сумму по количеству. То есть количество проданного товара в штуках равно количеству закупленного товара в штуках по этому месяцу.
2. Делаем из себестоимости начальную продажную цену (12% + НДС). Вот её мы будем варьировать.
3. Умножаем среднее количество продаж за день на начальную цену - получаем частичную сумму дневных продаж одного продукта.
И так делаем по каждому продукту, который закупался в этом месяце (вот, к слову, и определили, какие продукты взять. Берём те, которые закупали).
Суммируем частичные дневные суммы (в рублях с копейками, вещественные числа) по всем продуктам. Получаем полную дневную сумму. Сравниваем с фактической суммой продаж.
Вот тут могут быть три варианта: больше, меньше, равно. Если равно, то подбор закончен. Количества в штуках есть, цены есть, количество, проданное за месяц, сходится с количеством закупленным и финансово, и количественно.

Если не равно, то мне нужно подумать, а также вспомнить, что делалось в старой программе. Потому что здесь для каждой частичной суммы будут выставляться границы.

Сообщение отредактировано: swf - 07.07.21, 22:11

Цитата

Возьмём данные, скажем, за самый первый месяц. Зафиксируем один продукт.
Мы знаем, сколько было закуплено в этом месяце и сколько возвращено. Будем считать, что за первый месяц мы продали всё: все закупки - все возвраты. То есть никакого остатка на начало след. месяца не было. Во всяком случае, из ваших данных этого не видно.
1. Весь товар, закупленный и не возвращённый в этом месяце, делим на число дней в месяце, округляем до целого. Делаем во все дни одинаково, в последний день так, чтобы набрать сумму по количеству. То есть количество проданного товара в штуках равно количеству закупленного товара в штуках по этому месяцу.
2. Делаем из себестоимости начальную продажную цену (12% + НДС). Вот её мы будем варьировать.
3. Умножаем среднее количество продаж за день на начальную цену - получаем частичную сумму дневных продаж одного продукта.
И так делаем по каждому продукту, который закупался в этом месяце (вот, к слову, и определили, какие продукты взять. Берём те, которые закупали).
Суммируем частичные дневные суммы (в рублях с копейками, вещественные числа) по всем продуктам. Получаем полную дневную сумму. Сравниваем с фактической суммой продаж.
Вот тут могут быть три варианта: больше, меньше, равно. Если равно, то подбор закончен. Количества в штуках есть, цены есть, количество, проданное за месяц, сходится с количеством закупленным и финансово, и количественно.

Если не равно, то мне нужно подумать, а также вспомнить, что делалось в старой программе. Потому что здесь для каждой частичной суммы будут выставляться границы.

Да отлично... хорошо!!!!!

swf
доброго времени суток!

Цитата

1. Весь товар, закупленный и не возвращённый в этом месяце, делим на число дней в месяце, округляем до целого. Делаем во все дни одинаково, в последний день так, чтобы набрать сумму по количеству.

Да соглашусь вы правы только в той части если все закупки и невозвраты продадутся, но в жизни такое не бывает часто... как бы это динамический процесс... поэтому и придумали термин "остатки". Нас инетерсует период и поэтому ненадо думать о другом периоде... смотрите период каждый период делится на 3 части:

1) начало дня - тут что осталось от вчерашнего допустим возьмем 2 продкута творог и молоко... творог-5шт, молоко-4шт. Это остатки и все.
2) это середина - тут будем или закупать если есть закупки или возврат если есть: допустим закупка молока-2шт, творога-0шт. Возврат молока-0шт, творог-1шт, ну и Продажа если были продажи молоко-2шт, творог-0шт.
3) конец дня - после всех операций что осталось по молоку и творогу... осталось молока=4+2-0-2=4шт, творога=5+0-1-0=4шт.

Все просто ведь. Но в нашем случае продажи не в штуках... только сумма тех продуктов которые купили чтото в штуках чтото в килограммах или в литрах, мы не знаем какой товар продался и сколько штук купили его.
Поэтому

Цитата

То есть количество проданного товара в штуках равно количеству закупленного товара в штуках по этому месяцу.

исходя что все же так не бывает что все продается что закупается без остатка в определенный период считаю неправдоподобным...

Решение задачи есть как я выше описывал... давайте сделаем так я вам дам массив сумм на вход и саму сумму к которой слагаемые массива должны в сумме приблизится к ней.... а вы скажете как решить эту проблему... остальное я решу... вобщем то вот моя проблема и есть то что надо найти сумму слагаемых которая должна быть максимально близка но не больше к данной сумме.

Вот массив слагаемых:

• 479.7, 935.36, 664.41, ................. 140.82, 3559.42, 1017.56

а Сумма к которой должно приблизится: 6268491.48

Сообщение отредактировано: test4me - 08.07.21, 09:04

Ну здесь гибридный алгоритм из первой статьи.
Самой программы у меня нет, т.к. её писала дипломница. Описание алгоритма - в статье.

Цитата

Ну здесь гибридный алгоритм из первой статьи.
Самой программы у меня нет, т.к. её писала дипломница. Описание алгоритма - в статье.

Все понятно спасибо огромное вам за время, умные идеи и описание алгоритма.... постараюсь к сроку если чтото получится надо успеть))))