Жадный алгоритм — обесценивание стоимости

Это проблема, которую я нашел в качестве дополнительного примечания в Algorithm Design Кляйнберга и Тардоса.

Предположим, мы пытаемся продать оборудование, стоимость которого амортизируется с коэффициентом ri ‹ 1 в месяц, начиная со 100 долларов, поэтому, если вы продадите его через t месяцев, вы получите 100,r< sub>ят.

Если вы можете продавать только один товар в месяц, в каком порядке их лучше всего продавать?

Вход (3/4; 1/2; 1/100)

Оптимальный порядок будет [100x{1/2+(3/4)2+(1/100)3}].

Я не уверен, как решить эту проблему.


optimization analysis algorithm math greedy
person user2761431    schedule 09.09.2013    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Предположим, что имеется N предметов с индивидуальным Ri.

  1. Вычислите матрицу N x N, где Cij = Power(Ri,j).

  2. Теперь проблема сводится к проблеме назначения с N объектами, которые должны быть размещены в N позициях, и каждый из них связан с соответствующей прибылью.

  3. Максимизируйте общую прибыль, используя любой алгоритм, такой как венгерский алгоритм.

person Abhishek Bansal    schedule 09.09.2013
comment
Я думаю, это продвинуто. Я искал жадный алгоритм. Я не могу оценить/проверить ваш ответ. Спасибо, в любом случае. - person user2761431; 09.09.2013

arrow_upward
0
arrow_downward

Жадный метод должен работать. Каждый месяц продавайте товар, максимизирующий Ri^month - Ri^(month+1). Это означает, что мы продаем товар, который потеряет наибольшую стоимость в течение следующего месяца.

В примере ввода:

  • 1/2 ^ 1 - 1/2 ^ 2 = 0.25
  • 3/4 ^ 1 - 3/4 ^ 2 = 0.1875
  • 1/100 ^ 1 - 1/100 ^ 2 = 0.0099

Итак, в первый месяц мы продаем товар с R = 1/2.

  • 3/4 ^ 2 - 3/4 ^ 3 = 0.046875
  • 1/100 ^ 2 - 1/100 ^ 3 = 0.000099

R = 3/4 в качестве второго пункта и 1/100 в конце.

Я не математик, поэтому я не могу дать вам доказательство, но довольно ясно, что это работает, если вы принимаете, что функции вида a^x-a^(x+1) = b^x-b^(x+1) имеют только одно решение.

person Santtu Keskinen    schedule 09.09.2013
comment
Похоже, это может сработать. Без доказательства Жадный алгоритм едва ли можно считать оптимальным решением. Я постараюсь разработать доказательство правильности. Спасибо. - person user2761431; 09.09.2013