Блог

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

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

 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)
 

Если сумма недоступна для заданных типов монет, вы оставляете ее значение как inf в массиве запомненных значений. Но inf также означает, что значение ранее не посещалось. То есть каждый раз, когда мы видим an 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()