Здравствуйте, попалась задача на динамику:
Нужно найти подмножество чисел A1, A2 .... An чтобы их произведение, взятое по модулю m, было максимально. И еще нужно уметь восстанавливать ответ. Подскажите идею динамики.
m < 10000
0 <= Ai <= 10000
n <= 100
Буду благодарен за помощь!
Коль ограничения на n и m невелики достаточно знать до каких чисел по модулю m можно добраться. То есть для каждого Ai переберём все числа по модулю m, до которых уже добрались, и обновим это множество. Для восстановления ответа необходимо хранить еще число, с помощью которого получилось прийти в текущее состояние. O(n*m).
Можно на примере пожалуйста?
Допустим,
m = 7
,n = 3
,A = [4, 2, 5]
.Условимся, что произведение пустого множества — единица. Изначально доступно лишь одно состояние динамики:
dp[1] = true
.Перебираем массив
А
.Для первого элемента:
1 * 4 % 7 = 4
, значитdp[4] = true
.Для второго элемента:
1 * 2 % 7 = 2
,4 * 2 % 7 = 1
, значитdp[2] = true
, аdp[1]
и так былоtrue
до этого.Для третьего элемента:
1 * 5 % 7 = 5
,2 * 5 % 7 = 3
,4 * 5 % 7 = 6
, значитdp[5] = true
,dp[3] = true
,dp[6] = true
.Максимальным произведением по модулю m получилось
6
.Для восстановления ответа в динамике нужно так же хранить число, с помощью которого пришли в это состояние, и для упрощения — состояние из которого пришли.
Для описанного теста это будет выглядеть так (с помощью какого числа пришли/откуда пришли):
dp[1] = { -, - }
dp[2] = { 2, 1 }
dp[3] = { 5, 2 }
dp[4] = { 4, 1 }
dp[5] = { 5, 1 }
dp[6] = { 5, 4 }
Определив максимальное достаточно лишь пройтись в обратную сторону по состояниям динамики до единицы.
То есть для описанного теста:
6 -> 4 -> 1
, а сам ответ:5 * 4
.Простите за ошибку. Ограничения я поменял.
Это ничего, потому что описанное решение работает за O(n*m).
С задачей о рюкзаке вы знакомы?
Неа