Проблема размена монет: подход сверху вниз не является полиномиальным

Проблема с раздачей монет (см. кодовую страницу leet здесь) дает нам несколько монет определенного номиналы в массиве, c. Затем, учитывая целевую сумму t, мы хотим найти минимальное количество монет, необходимое для получения этой целевой суммы. В принципе, это очень похоже на задачу оптимального разрезания стержня, описанную в разделе 15.1 книги «Введение в алгоритмы» Кормена и др.

В соответствии с их подходом я реализовал нисходящую и восходящую версии проблемы размена монет. Восходящий подход работает довольно хорошо и решает все тестовые случаи довольно быстро. Однако версия сверху вниз занимает очень много времени на определенных входных данных, что предполагает, что она не является полиномиальной на входных данных. Он дает правильный ответ для тестовых случаев, которые ему удается решить. Кто-нибудь знает, почему он не может быть полиномиальным? Или существенно медленнее, чем восходящая версия?

def memoised_coin_chg(c,u):
  r=np.ones(u+1)*np.inf
  r[0]=0
  return memoised_coin_chg_aux(c,u,r)

def memoised_coin_chg_aux(c,u,r):
  if r[u]<np.inf:
      return r[u]
  if u==0:
      q=0
  else:
      q=np.inf
      for i in range(len(c)):
          if u >= c[i]:
              q=min(q,memoised_coin_chg_aux(c,u-c[i],r))
  r[u]=q+1
  return q+1

def tst3():
  res=memoised_coin_chg([1,2,5],11)
  print(res)
  res=memoised_coin_chg([2],3)
  print(res)
  res=memoised_coin_chg([1,2147483647],2)
  print(res)
  ## Too slow to produce results from here on..
  res=memoised_coin_chg([27,40,244,168,383],6989)
  print(res)
  res = memoised_coin_chg([186,419,83,408],6249)
  print(res)
  res = memoised_coin_chg([282,116,57,239,103,89,167],4856)
  print(res)

python dynamic-programming coin-change
person Rohit Pandey    schedule 14.12.2020    source источник

Ответы (1)


arrow_upward
1
arrow_downward

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

Итак, если вы хотите составить этот полином, вам нужно различать inf, что означает «не посещено», и inf, что означает «посещено, но недоступно». Мое предложение будет использовать -1 для не посещенных значений:

import numpy as np;

def memoised_coin_chg(c,u):
  r=np.ones(u+1)* -1 # change 1
  r[0]=0
  return memoised_coin_chg_aux(c,u,r)

def memoised_coin_chg_aux(c,u,r):
  if r[u] != -1: # change 2
      return r[u]
  # removed u = 0 check because r[0] is already initialized to 0
  q=np.inf
  for i in range(len(c)):
      if u >= c[i]:
          q=min(q,memoised_coin_chg_aux(c,u-c[i],r))
  r[u]=q+1
  return q+1

def tst3():
  res=memoised_coin_chg([1,2,5],11)
  print(res)
  res=memoised_coin_chg([2],3)
  print(res)
  res=memoised_coin_chg([1,2147483647],2)
  print(res)
  ## Too slow to produce results from here on..
  res=memoised_coin_chg([27,40,244,168,383],6989)
  print(res)
  res = memoised_coin_chg([186,419,83,408],6249)
  print(res)
  res = memoised_coin_chg([282,116,57,239,103,89,167],4856)
  print(res)

tst3()
person Cem    schedule 29.12.2020