Динамическое программирование - изменение алгоритма резки стержня снизу вверх

Я немного запутался в том, как изменить алгоритм стержня с разрезом снизу вверх, чтобы включить фиксированную стоимость c для каждого разреза. Выручка представляет собой сумму цены штук за вычетом себестоимости. У меня есть что-то подобное, но я не уверен, что я на правильном пути.

MODIFY-BOTTOM-UP-CUT-ROD(p,n)
1.  let r[0..n] be a new array
2.  r[0] = 0
3.  for j = 1 to n
4.     q = -INF
5.     for i = 1 to j
6.        q = max(q,p[i] + r[j-i] - c)
7.     r[j] = q
8.  return r[n]

algorithm dynamic-programming bottom-up
person tom3322    schedule 08.04.2014    source источник
comment
Уточните, пожалуйста, проблему оптимизации, которую необходимо решить; вы имеете в виду следующую проблему? faculty.ycp.edu/~dbabcock/cs360/lectures/lecture12.html< /а>   -  person Codor    schedule 08.04.2014
comment
Вы на верном пути. Ваш также делает то, что вы хотите.   -  person user3401643    schedule 08.04.2014
comment
ваш подход правильный   -  person    schedule 05.01.2015

Ответы (1)


arrow_upward
0
arrow_downward

Вам нужно внести изменения, чтобы включить вариант использования, при котором не будет производиться никаких сокращений, при котором не будет понесена фиксированная стоимость «с».

Модификации

4. q = p[j]
5. for i = 1 to j-1

Пояснения

Строка 4: Здесь при инициализации -inf будет пропущен вариант использования, когда общая стоимость исключает фиксированную стоимость.

Строка 5: случай, когда i равно j, включен в инициализацию в строке 4.

Источник: http://ranger.uta.edu/~huang/teaching/CSE5311/HW3_Solution.pdf

person Chaipau    schedule 03.02.2019