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

Все остальные условия остаются как в предыдущих постах.
Другими словами:
Условие.
Дано 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

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

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