Project Euler # 219

Question

Я пытаюсь выполнить проект Эйлера № 219, но я не понимаю его. Я пытаюсь использовать Python, который, согласно проекту Эйлера, сможет сделать это в течение минуты! Это заставляет меня думать, что они не могут хотеть, чтобы я вычислил каждую отдельную битовую строку, поскольку это было бы слишком медленным в Python - должен быть алгоритм sub O (n).

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

cost(1) = 1 
cost(2) = 5 
cost(3) = 11 
cost(4) = 18 
cost(5) = 26 
cost(6) = 35 
cost(7) = 44 
cost(8) = 54 
cost(9) = 64 
cost(10)= 74 
cost(11)= 85 
cost(12)= 96 

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

1 
01 
001 
0001 
00001 
00000 

Но это не оптимально для более чем 7 битстрон. Может ли кто-нибудь вести меня в том, что я должен рассматривать?

Answer 1

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

[Изменить] При дальнейшем рассмотрении кажется, что вы не можете построить дерево Хаффмана на узлах N с определенными частотами, поскольку функция стоимости для строки равна 4 * (# из 1) + (# из 0). Если функцией стоимости была длина строки (или ее несколько), вы могли бы создать дерево Хаффмана.

Любой набор кодов без префикса может быть представлен как двоичное дерево, подобное Хаффману, где каждый узел имеет 0 или 2 детей, а листовые узлы представляют собой коды. Учитывая дерево с N узлами, мы можем построить дерево с N + 1 узлов следующим образом:

1. Выберите листовой узел с наименьшей стоимостью, где стоимость узла листа 4 * (# 1 на путь от корня к листьям) + (# от 0 на пути)
   • Добавьте 2 детей в этот узел

Таким образом, если код узла был ранее хххх, то удалить, что код из нашего набора кода (поскольку он больше не является листом) и добавьте два кода xxxx0 и xxxx1. Общая стоимость набора кодов теперь увеличена на

стоимость (xxxx0) + стоимость (xxxx1) - стоимость (xxxx) = стоимость (0) + стоимость (1) + стоимость (xxxx) = 5 + стоимость (xxxx)

Следовательно, mincost (N + 1) < = mincost (N) + 5 + стоимость (самый дешевый код в лучшем решении для N). Моя теория заключается в том, что неравенство должно быть равенством, но я еще не смог его доказать. Для всех значений, которые вы указали, которые вы принудительно перенаправляете, это утверждение на самом деле является равенством.

Если это равенство, то решить эту проблему, что вы могли бы сделать это:

1. Начать с пустым кодом, установленным на общую сумме нулевой
   • Итерации от 1 до 10 , сделайте следующее:
     1. Найти дешевый код в код установлен
   • Split этот код в два, добавляя 0 и 1
   • Добавить стоимость этого кода + 5 к общей стоимости

Если вы используете priority queue, вы должны быть в состоянии сделать это в O (N log N). Это может быть или не быть осуществимым, учитывая верхний предел 10 .

Answer 2

Как я его решил, вычислил стоимость (n) до n = 1000, а затем просто угадал, как это исходит оттуда. Если вы посмотрите на различия между последовательными значениями и используете The encyclopedia of integer sequences (и некоторое воображение), вы можете догадаться об этом правиле.

Вы можете вычислить небольшие (< = 1000) примеры с помощью своего рода динамического программирования с использованием повторения Cost(n) = min {Cost(k)+Cost(n-k)+k+4*(n-k) | 0 < k < n}.

Answer 3

Адам: Спасибо за ссылку - это выглядит очень многообещающий! Я не уверен, что после прочтения статьи в Википедии учитывается коэффициент 4. Я пытаюсь «сопоставить» проблему Project Euler с алгоритмом. Алфавит должен был быть длиной 10^9, но какой вес был бы?

Другое дело, что беспокоит меня то, что кодирование Хаффмана является в лучшем случае O (N), конечно, будучи слишком медленно, как я уже говорил выше ...

mattiast: Я не думаю, что ваши повторения работы (или я не понимайте это!). Моя интерпретация этого является:

def cost(n): 
    if n == 1: return 1 

    m = None 
    for k in range(1, n): 
     v = cost(k)+cost(n-k)+k+4*(n-k) 
     if not m or v < m: m = v 

    return m 

print(cost(6)) 

Значение возвращается в 41, когда оно должно быть 35. И все же, если мои ценности являются правильными, то я не могу найти различия в АТТ в Integer последовательностях энциклопедии.

Answer 4

Решение Адама Розенфилда выглядит очень вероятно работать. Уже поздно (около полуночи!), Так что я оставлю это до утра. У меня есть эффективная реализация очереди приоритетов в C, поэтому завтра я попытаюсь использовать ее и найти решение.

Я расскажу об успехах алгоритмов, но рассуждения кажутся мне полезными, и он точно соответствует данным (как сказано выше). Однако, продолжая бормотать, должен быть алгоритм sub O (n)! ;-)

Answer 5

Оказывается, что O [n * log (n)] не слишком медленный, но сложность памяти, которая приблизительно равна O (n). Однако предложенный выше алгоритм может быть уменьшен до O (n) временной сложности и низкой сложности памяти. Для этого можно использовать массив x, для которого x [a] = число числовых значений стоимости a.

Сделанные допущения дают правильный результат для 10^9, поэтому я считаю, что они верны.

Answer 6

N = 10 ** 9

т = [0]

для с в xrange (N): м = мин (т) t.remove (м) t.append (m + 1) t.append (m + 4) print sum (t), t