Изменение размера подмножества

Question

Задано целое число n и s различных размеров, но с положительными по возрастанию номерами от 0 до s_i в качестве элементов. Пусть хорошая сумма определяется здесь как a_1 + a_2 + ... + a_s = n. Подсчитайте, сколько сумм существует, когда вы берете за каждый a_i элемент из соответствующего набора s_i.

Я пытался генерировать любые возможные пути и опускать те, которые являются omittable, то есть когда у вас есть, например s=3, n=1 и вы получаете наборы s_0={0,1}, s_1={0,1,2,3}, s_2={0,1,2}, то вы можете опустить чек на сумму 0 + 0 + a_3 так a_3 не сможет быть достаточно большим. Я применил решение динамического программирования для нормальной суммы подмножества для каждой из этих возможных последовательностей, однако я получаю гораздо большие результаты, чем должен, и очень медленный.

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

Answer 1

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

dp[i] = dictionary of sums we can obtain using the first i sets and their counts 


dp[0, <elements in s[0]>] = 1 
for i = 1 to s - 1: 
    for each element x in dp[i - 1]: 
    for each element k in s[i]: 
     dp[i, x + k] += dp[i - 1, x] 

Сложность будет довольно большим, но там не так много вы можете сделать, чтобы уменьшить его, я думаю. Это должно сработать.

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

код Python:

def solve(s, n): 

    dp = [dict()] * len(s) 

    for k in s[0]: 
     dp[0][k] = 1 
    for i in range(1, len(s)): 
     dp[i] = dict() 
     for x in dp[i - 1]: 
      for k in s[i]: 
       if x + k in dp[i]: 
        dp[i][x + k] += dp[i - 1][x] 
       else: 
        dp[i][x + k] = dp[i - 1][x] 

    return dp[len(s) - 1][n] 

print(solve([[0,1,2],[0,1,2]], 3)) # prints 2 
print(solve([[0,1,2],[0,1,2,3,4],[0,1,2,3,4]], 5)) # prints 13