Уменьшить сумму разностей между соседними элементами массива

Это можно сделать с помощью динамического программирования. Просто создайте следующую структуру данных.

by position in the array
    by current hunger level (after distributing food)
        by total food left
            smallest sum of differences so far

Этого достаточно, чтобы узнать, какая наименьшая сумма находится в конце массива.

При желании также отслеживайте:

            # of ways to achieve smallest hunger level

Это позволит вам узнать, сколько способов получить эту наименьшую сумму.

При желании также отслеживайте:

            list of previous hunger levels that can achieve it

И теперь вы можете реконструировать все решения, которые этого достигают.

Я оставлю вам возможность сделать это на самом деле. (В моей истории есть много примеров решения подобных задач.)

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

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

2 sandwiches
2 4 4 3 4 5
          ^ Cost 1 reduces by 1
            but prevents further
            reductions.

  ^^^ Cost 2, reduces by 2.

Я не уверен, существует ли общее решение с полиномиальным временем, потому что в конечном итоге выбор заключается в некотором разделении «холмов», которое нужно уменьшить (имеется в виду как минимум три последовательных элемента, где все средние элементы больше, чем крайний левый и крайний правый; или конец массива секции, если они выше своего соседа). У нас может быть динамическая программа, основанная на индексе, уровне голода и оставшихся бутербродах, как кратко описано, где последнее зависит от диапазона значений.

Сумма абсолютных разностей уменьшается только при уменьшении локального максимума.

Если вы уменьшите максимум на любом конце, сумма разностей уменьшится на единицу, например [3,2,1] -> [2,2,1].

Если вы уменьшите максимум посередине, сумма разностей уменьшится на два, например [1,3,2] -> [1,2,2].

Если максимум уменьшается, он может объединиться с другим максимумом, который вы можете уменьшить, но новый максимум никогда не будет более дешевым или экономически эффективным. Он может быть только шире, например [1,3,2] -> [1,2,2].

Таким образом, оптимальная стратегия состоит в том, чтобы многократно сокращать наиболее экономически эффективный максимум, с точки зрения benefit/width, который у вас есть достаточное количество бутербродов, чтобы сократить его. benefit — 1 для максимумов на концах или 2 для максимумов в середине.

Остановитесь, когда у вас уже не будет достаточного количества бутербродов, чтобы уменьшить самый узкий максимум.

Вы можете сделать это за время O(n), найдя все максимумы и поместив их в приоритетную очередь, чтобы обрабатывать их в правильном порядке по мере их уменьшения.

O(n log n) — это просто. Чтобы сделать эту привязку O(n), вам нужно будет использовать приоритетную очередь с подсчетом и сортировкой вместо кучи. Вам также нужно быть немного умнее, отслеживая области массива, которые, как известно, находятся на одной высоте, чтобы вы могли объединить их за постоянное время.

Вот реализация O (n) в Python

def distribute(arr):

    foodLeft = arr[0]
    hungers = arr[1:]

    # For each element in hungers, calculate number of adjacent elements at same height
    spans = [1] * len(hungers)
    for i in range(1, len(hungers)):
        if hungers[i-1]==hungers[i]:
            spans[i] = spans[i-1]+1
    for i in range(len(hungers)-2, -1, -1):
        if hungers[i+1]==hungers[i]:
            spans[i] = spans[i+1]

    # spans are identified by their first element.  Only the counts and hungers on the edges need to be correct

    # if a span is a maximum, it's height.  Otherwise 0
    def maxHeight(left):
        ret = len(spans)
        if left > 0:
            ret = min(ret, hungers[left] - hungers[left-1])
        right = left + spans[left]-1
        if right < len(spans)-1:
            ret = min(ret, hungers[right] - hungers[right+1])
        return max(ret,0)
    
    # change the height of a span and return the maybe new span that it is a part of
    def reduce(left, h):
        right = left + spans[left] - 1
        hungers[left] -= h
        hungers[right] = hungers[left]
        if right < len(spans)-1 and hungers[right+1] == hungers[right]:
            # merge on the right
            w = spans[right+1]
            spans[right] = spans[right+1] = 0 # for debuggability
            right += w
        if left > 0 and hungers[left-1] == hungers[left]:
            # merge on left
            w = spans[left-1]
            spans[left] = spans[left-1] = 0 # for debuggability
            left -= w
        spans[left] = spans[right] = right - left + 1
        return left
    
    def isEdge(left):
        return left < 1 or left + spans[left] >= len(spans)
    
    # constant-time priority queue for non-edge spans
    # it's just a list of spans per width
    pq = [[] for _i in range(len(spans)+1)]

    # populate priority queue
    curspan = 0
    while curspan < len(spans):
        width = spans[curspan]
        if maxHeight(curspan) > 0 and not isEdge(curspan):
            pq[width].append(curspan)
        curspan += width

    # this will be True at the end if we can sacrifice one edge max selection to get one
    # mid max selection, which would produce one more point
    canBacktrack = False
    # process mid spans in order
    curpri = 1
    # while not all hungers are the same
    while spans[0] < len(spans):

        # find the best middle maximum
        bestmid = None
        midwidth = None
        if curpri < len(pq) and curpri <= foodLeft:
            if len(pq[curpri]) == 0:
                curpri += 1
                continue
            bestmid = pq[curpri][-1]
            midwidth = spans[bestmid]

        # find the best edge maximum
        bestedge = None
        edgewidth = None
        if maxHeight(0) > 0 and foodLeft >= spans[0]:
            bestedge = 0
            edgewidth = spans[0]
        r = len(spans)-spans[-1]
        if maxHeight(r) > 0 and foodLeft >= spans[r] and (bestedge == None or spans[r] < edgewidth):
            bestedge = r
            edgewidth = spans[r]

        # choose
        bestspan = None
        h = 0
        if bestedge == None:
            if bestmid == None:
                break
            bestspan = bestmid
            bestwidth = midwidth
            canBacktrack = False
        elif bestmid == None:
            bestspan = bestedge
            bestwidth = edgewidth
            canBacktrack = False
        elif midwidth <= edgewidth*2:
            # mid maximum is more cost effective
            # OR choo
            bestspan = bestmid
            bestwidth = midwidth
            canBacktrack = False
        else:
            bestspan = bestedge
            bestwidth = edgewidth
            # tentative
            canBacktrack = True
        
        if bestspan == bestmid:
            # chose the middle span -- remove from pq
            pq[curpri].pop()

        # how much we can reduce this maxium by
        h = min(foodLeft//bestwidth, maxHeight(bestspan))
        foodLeft -= bestwidth*h
        canBacktrack = canBacktrack and foodLeft < midwidth and foodLeft + edgewidth >= midwidth
        bestspan = reduce(bestspan, h)
        if maxHeight(bestspan) > 0 and not isEdge(bestspan):
            pq[spans[bestspan]].append(bestspan)
    
    # finally, calculate the new total diffs
    totaldiff = 0
    curspan = spans[0]
    while curspan < len(spans):
        totaldiff += abs(hungers[curspan] - hungers[curspan-1])
        curspan += spans[curspan]
    if canBacktrack:
        totaldiff -= 1
    return totaldiff

# test
cases = [
    [8, 11, 14, 15, 16, 13, 2, 3],
    [7, 5, 4, 3, 4, 5, 2, 3, 1, 4, 5],
    [2, 4, 4, 3, 4, 5],
    [3, 3, 4, 4, 4, 3, 4],
    [4, 3, 4, 4, 4, 3, 5],
    [5, 3, 4, 4, 4, 3, 6],
    [3, 3, 4, 4, 3, 4, 5]
]
for case in cases:
    print("{0}: {1}".format(case, distribute(case)))

Вот решение для динамического программирования на Ruby, которое, ввиду сходства Ruby и Python, можно довольно легко перевести на Python. ¹ Возможно, именно эту модель динамического программирования имел в виду @btilly в своем ответе.

def opt(nbr_sands, hlevels)
  arr = Array.new(hlevels.size) { Array.new(nbr_sands+1) }
  (0..nbr_sands).each do |sands_left|
    arr[0][sands_left] = hash_person_0(nbr_sands-sands_left, hlevels.first)
  end
  (1..hlevels.size-1).each do |p|
    (0..nbr_sands).each do |sands_left|
      arr[p][sands_left] = hash_person_p(nbr_sands, sands_left, hlevels[p],
        hlevels[p-1], arr[p-1])
    end
  end
  arr
end

def hash_person_0(sands_for_person_0, hlevel)
  val = sands_for_person_0 <= hlevel ? 0 : Float::INFINITY
  { sands_for_person_0 => { val: val, opt_prev_sands: nil } }
end 

def hash_person_p(nbr_sands, sands_left, hlevel, prev_hlevel, prev_arr )
  max_sands_to_p = [nbr_sands - sands_left, hlevel].min
  (0..max_sands_to_p).each_with_object({}) do |sands_to_p, h|
    adj_hlevel = hlevel - sands_to_p
    prev_sands_left = sands_left + sands_to_p
    n, d = prev_arr[prev_sands_left].min_by do |n,d|
      d[:val] + (adj_hlevel - (prev_hlevel - n)).abs
    end
    val = d[:val] + (adj_hlevel - (prev_hlevel - n)).abs 
    h[sands_to_p] = { val: val, opt_prev_sands: n }
  end
end

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

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

Здесь Принцип оптимальности Беллмана требует, чтобы при любой из переменных состояния для человека p оптимальное распределение сэндвичей остальным людям не зависело от распределения сэндвичей лицам, предшествующим человеку p, который дал повышение данному состоянию. переменная для человека p. Это требование явно удовлетворено.

Предполагать

nbr_sands = 2
hlevels = [3, 2, 1]

Очевидно, что существуют два оптимальных распределения:

[1, 1, 1]

и

[1, 0, 0]

То есть лица 0 и 1 должны получить 1 сэндвич, а человек 2 не должен получить ни одного (снижение [3, 2, 1] до [2, 1, 1]), или человек 0 должен получить 1 сэндвич, а люди 1 и 2 не должны получить ни одного (сокращение [3, 2, 1] до [2, 2, 1]), что дает оптимальные значения 1 в обоих случаях.

Для этих значений nbr_sands и hlevels

opt(nbr_sands, hlevels)

возвращает следующий (аннотированный) массив arr, где arr[p][n] соответствует хэшу, связанному с человеком p (основание ноль), когда сэндвичи n остаются после всех распределений между людьми до человека p включительно. Я объясняю значение этих хэшей ниже.

[
  # p = 0 #
  [
    {2=>{:val=>0, :opt_prev_sands=>nil}},
    {1=>{:val=>0, :opt_prev_sands=>nil}}, # * and **
    {0=>{:val=>0, :opt_prev_sands=>nil}}
  ],

  # p = 1
  [
    # sands_left = 0
    {
      0=>{:val=>1, :opt_prev_sands=>2},
      1=>{:val=>1, :opt_prev_sands=>1}, # * prev sands left = 0 + 1 = 1, prev sands = 1
      2=>{:val=>3, :opt_prev_sands=>0}
    },
    # sands_left = 1
    {
      0=>{:val=>0, :opt_prev_sands=>1}, # * prev sands left = 1 + 0 = 1, prev sands = 1
      1=>{:val=>2, :opt_prev_sands=>0}
    },
    # sands_left = 2
    {
      0=>{:val=>1, :opt_prev_sands=>0}
    }
  ],

  # p = 2
  [
    # sands_left = 0
    {
      0=>{:val=>1, :opt_prev_sands=>1}, # * prev sans_left = 0 + 0 = 0, prev sands = 1
      1=>{:val=>2, :opt_prev_sands=>0}
    },
    # sands_left = 1
    {
      0=>{:val=>1, :opt_prev_sands=>0}, # ** prev sans_left = 1 + 0 = 1, prev sands = 0
      1=>{:val=>3, :opt_prev_sands=>0}
    },
    # sands_left = 2
    {
      0=>{:val=>2, :opt_prev_sands=>0}
    }
  ]
]

Теперь мы можем найти оптимальное решение, начиная с конца, с человеком p = 2.

Нас интересует, какая комбинация sandwiches left и присвоения человеку 2 минимизирует значение :val в связанном хэше.

Их два, обозначены * и **. Обычно мы заинтересованы в поиске оптимального решения только в том случае, если их несколько. Итак, давайте посмотрим на файл, отмеченный *. Это соответствует

arr[2][0][0]
  #=> {:val=>1, :opt_prev_sands=>1}

Первый [0] соответствует тому, что осталось ноль бутербродов; последний [0] возвращает значение хеша, когда человеку 2 выдается ноль бутербродов. Это означает, что количество бутербродов в начале периода 2 и, следовательно, в конце периода 1 равно 0 + 0 #=> 0, а оптимальное количество бутербродов, данное человеку 1, равно 1.

Это означает, что нам далее необходимо изучить

arr[1][0][1]
  # {:val=>1, :opt_prev_sands=>1}

Это означает, что количество сэндвичей, оставшихся после распределения человеку 1, равно 0 + 1 = 1 и человек 0 должен получить 1 сэндвич. Таким образом, одно оптимальное решение даёт [1, 1, 0], снижая уровень голода до [3-1, 2-1, 1-0] #=> [2, 1, 1].

Я оставлю читателю упражнение по вычислению второго оптимального решения.

^{1. I am in the process of teaching myself Python and as part of the endeavior will in time edit my answer to give the equivalent solution in Python.}