Найдите последовательность с максимальной вероятностью
Я работаю над следующей проблемой:
Дан набор элементов ={1,2,3,4,5,6,7,8,9,....,100} и набор типов элементов ={a,b,c,d,e,f,g} и набор вероятностей, прикрепленный к каждому элементу s P (1_a) = 0,4, P(2_b) = 0,6, P(3_c) = 0,4, P(4_a) = 0,9, ..., P(100_f) = 0,9 и так далее. Видите ли, каждый элемент имеет тип, заданный ранее определенным набором.
Найдите две последовательности S1 и S2 с максимальной вероятностью:
так что чистое количество типов элементов в пределах разницы между двумя последовательностями S1 и S2 не превышает 20% длины, полученной суммой двух последовательностей.
например: (Итак, если одна последовательность имеет длину 5, что означает, что 20% - это частота 1, и мы дали S1 = 'aabdd' и S2 = 'fgaec'; это не будет выполнять условия из-за чистого количества элементов с типом a = 2-1 = 1 и элементы с типом d = 2-0 = 2. Таким образом, существует более 20% элементов с одинаковым типом (2 элемента типа d) в разнице двух последовательностей.
Сейчас я ищу алгоритм, чтобы найти наиболее вероятную последовательность при заданных условиях. Может ли кто-нибудь помочь мне разобраться в этом, возможно, применив прямой проход в конечном автомате. Решается ли это за подходящее время?
Спасибо за помощь;)