Блог

Вопрос: Учитывая множество целых чисел, найдите максимальное число, которое мы можем получить как сумму подмножества этих целых чисел, так что никакие 2 целых числа не имеют абсолютной разницы в 1

Например:

1. Если мультисет [1,1,2,3,3,3,4,4,5,5,5,15] ,
   то максимальная сумма равна (1 1 3 3 3 5 5 5 = 26)
2. Если мультисет [3,3,4,4,4,5,5,5,5,6,6,10,20] ,
   то максимальная сумма равна (3 3 5 5 5 5 10 20 = 56)

Моя попытка:

Это похоже на другой вопрос, связанный с нахождением подмножества с максимальной суммой таким образом, чтобы никакие два элемента не были смежными друг с другом. Для этого конкретного вопроса я использовал подход динамического программирования и использовал тот же подход, чтобы попытаться решить этот вопрос, но безуспешно. Любая помощь будет очень признательна!

   from collections import Counter
  def max_sum(nums):
    c = Counter(nums)
    N = sorted(set(nums))
    if len(N) == 0:
      return 0
    if len(N) == 1:
      return c[N[0]]*N[0]
    if len(N) == 2:
      return max(c[N[0]]*N[0], c[N[1]]*N[1])

    dp = [0] * len(N)
    dp[0] = c[N[0]]*N[0]

    if (N[1] - N[0]) == 1:
      dp[1] = max(c[N[0]]*N[0], c[N[1]]*N[1])
    else:
      dp[1] = sum([c[N[0]]*N[0], c[N[1]]*N[1]])

    for i in range(2, len(N)):
      if (N[i] - N[i-1]) == 1:
        dp[i] = max(c[N[i]]*N[i]   dp[i-2], dp[i-1])
      else: 
        dp[i] = dp[i-1]   c[N[i]]*N[i]
      
    return dp[-1]
  
  max_sum([1,1,1,5,5,5,6,6,6])