На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
Страницы: (6) 1 [2] 3 4 ... Последняя » все  ( Перейти к последнему сообщению )  
> Набор суммы минимальным числом слагаемых, динамическое программирование
    Все остальные условия остаются как в предыдущих постах.
    Другими словами:
    Условие.
    Дано N целых положительных слагаемых, целое положительное число B.
    Вопрос.
    Набрать сумму, минимально отклоняющуюся от B (с недостатком). Если таких наборов несколько, выбрать решение с минимальным числом слагаемых. Выбрать вариант с заданным числом слагаемых.
      можно построить решение динамическим программированием - заполнить двумерную таблицу из M строк и B столбцов, где M - число слагаемых.
        Цитата
        можно построить решение динамическим программированием - заполнить двумерную таблицу из M строк и B столбцов, где M - число слагаемых.

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

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

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

        я имею ввиду как определить в какую именно строку записывать слагаемое
          безо всякой оптимизации со сложностью O(NMonet * Sum * Length(Data))
          ExpandedWrap disabled
            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)
            Это великолепно!!!
            Огромнейшее спасибо. Вы даже не представляете как помогли мне.
              Единственное улучшение, можно обойтись одномерным массивом (ну или двумерным, но один из размеров фиксированный). Переменный - набираемая сумма. В каждом элементе хранить последнюю добавленную монету. Можно заметно ускорить, если номиналов монет мало по сравнению с количеством монет, храня также количество добавленных монет. Тогда потребуется число проходов, равное количеству номиналов.
              ExpandedWrap disabled
                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 -
                Пыталась написать одномерным массивом, но не получилось :( То ли ДП тяжело даётся, то ли на работу после отпуска тяжело выходить. А вот если выкинуть эти массивы, и писать честной-благородной рекурсией, то даже думать не нужно.
                Тока рекурсией наберётся одна-единственная заданная сумма, поэтому слова "или ближайшую к ней" из песни придётся выкинуть.
                  Ну мой пример (Python), используя "массив" (N+1)*2, набирает наиболее близкую сумму за два прохода (два вида монет) по массиву. Правда как только я его написал, он у меня сразу за пределы массива вылетел, пришлось проходы немного укоротить.
                  При необходимости количество монет каждого номинала можно ограничить.
                  В списке монет порядок задает предпочтение по их использованию.

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

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

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

                    ExpandedWrap disabled
                      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 @
                      Рекурсией как раз можно определить все возможные варианты. Даже если требуемая сумма недостижима. Правда, работать алгоритм будет медленнее.

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

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

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

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

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

                                Начинать не с нуля, а с "каждой монеты по штуке". Если решение не найдено, следующая итерация "каждой монеты, кроме одной, по штуке"... и т.д.. до решения.
                                1 пользователей читают эту тему (1 гостей и 0 скрытых пользователей)
                                0 пользователей:


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,0789 ]   [ 14 queries used ]   [ Generated: 23.07.21, 17:19 GMT ]