Subset sum with repetitions

Информатика
1

Допустим нам дана последовательность целых неотрицательных чисел. Какое количество вариантов выбрать некоторые числа из этой последовательности, таких что можно было бы получить число S из суммы состоящей только из этих чисел, то есть если в последовательности число x встречается один раз то в сумме оно может встречатся сколько угодно раз. Возможно ли это решить используя динамику? Если да то можете помочь?
К примеру:
Последовательность: {1, 2, 4}
S = 4
Ответ: 4
Валидными суммами являются {1, 1, 1, 1}, {1, 1, 2}, {2, 2}, {4}

1 лайк
3

Какие ограничения на числа и на длину последовательности?

4

Длинна последовательности 100
Само число 1000

1 лайк
5

В этом случае задачу можно сдать используя “рюкзак”. Это тема в динамическом программировании.

1 лайк
6

Да просто не знаю что делать с тем что вещи могут повторяться

2 лайка
7

dp[x] = кол во способов собрать сумму x
У тебя будет “n слоев” (поидее можно и двумерным дп, но не меняет сути )
Берешь значения из этого же слоя так как элементы могут встречаться сколько угодно раз.

void solve() {
    int n, s;
    cin >> n >> s;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = a[i]; j <= s; j++) {
            dp[j] += dp[j - a[i]];
        }
    }
    cout << dp[s];
}
1 лайк
8

Вот пусть у тебя есть бесконечно количество предмета x, какие суммы можно получить?

1 лайк
9

Подумай почему в обычном рюкзаке мы обходили именно в таком порядке(По убыванию суммы)? На что это влияло?

1 лайк
10

Ааа тип когда обратно идем мы берем предыдущие значения(предыдущего предмета), а тут берем значении динамики текущего предмета