时间戳

首页 > 解决方案 > 带记忆的动态编程无法正常工作

python - 带记忆的动态编程无法正常工作

问题描述

我对使用动态编程的优化问题有一个粗略的解决方案。目的是在最短的时间内达到最大的满意度，每个项目都有单独的时间值，以及所有满意度的一般最佳时间。

def pp(list1, values, time_values, optimal_time, memo):
  list4 = []

  for i, j in zip(values, time_values):
    if (i,j,optimal_time) not in memo:
      memo[i,j,optimal_time] = (i * (optimal_time/j))
      list4.append(memo[i,j,optimal_time])

  zipped_lists = zip(list4, list1)
  sorted_pairs = sorted(zipped_lists)

  tuples = zip(*sorted_pairs)
  list4, list1= [list(tuple) for tuple in  tuples]
  return list(reversed(list1))

def getPP (list1, values, time_values, optimal_time):
  memo = {}
  return pp(list1, values, time_values, optimal_time, memo)

情况1：print(getPP(["LOK", "MP", "HM", "AR", "SG", "VV"], [0.37, 0.87, 0.27, 0.87, 0, 0.56], [6, 1, 15, 3, 3, 3], 6))

结果：['MP', 'AR', 'VV', 'LOK', 'HM', 'SG']

该解决方案似乎在某些情况下有效。

当我尝试这个时，它省略了数组中的最后一项，我的结果是：

案例2：print(getPP(["ARD", "AR", "GS", "LP", "MP", "ML", "SI", "VV"], [0.44, 0.67, 0.67, 0.5, 0.08, 0.44, 0.33, 0.87], [2, 3, 3, 4, 1, 5, 3, 3], 6))

结果：['SI', 'AR', 'ARD', 'GS', 'ML', 'MP', 'LP']

我不确定问题出在哪里。

标签： pythonoptimizationdynamic-programmingmemoization

解决方案

推荐阅读