исал программу для генерации суммы подмножества, которая может быть использована в этой задаче, которая гласит:

Предположим, у вас есть 3 $ 1-монеты, 2 $ 2-монеты, 3 $ 5-монеты, 1 $ 10-монета, есть 4 способа получить $ 10 из этих монет. Если существует n1 $ X1 монет, n2 $ X2 монет .... nm $ Xm монет, сколько способов мы можем получить $ X из этого ограниченного числа монет?

Если мы создадим набор {X1, X1 ..... X1, X2, X2 .......... X2, ..., ..., .......... .., Xm, Xm ... Xm}, а затем запустите на нем суммирование подмножеств, конечно, мы можем получить результат для $ X. Но я не мог найти способ использовать наборы {n1, n2, n3 .... nm}, {X1, X2, X3 .... Xm}. Друг сказал мне, что это вариация проблемы с рюкзаком, но я не уверен, как.

Это частичный код того, что я написал:

ways[0]=1, mylim=0;
for(i=0;i<count;i++){
    if(mylim+coins[i]<=LIMIT) mylim+=coins[i];
    else mylim=LIMIT;

    for(j=mylim; j>=coins[i];j--){
        ways[j]=(ways[j]+ways[j-coins[i]])%MOD;
    }
}

Было бы здорово для меня, если вы достаточно любезны, чтобы объяснить немного подробно.

РЕДАКТИРОВАТЬ: Этот вопрос больше подходит для стекового обмена для информатики, но, поскольку это мой старый вопрос, я его скорее редактирую.

Эта проблема может быть решена сВключение Исключение принцип, и это пригодитсякогда у нас есть фиксированные значения монет, но количество каждой монеты зависит от запроса.

Предположим,пути [v] это способы сделать$ v с$ x1, $ x2..$ хткаждый из которых используется столько раз, сколько необходимо. Теперь, если мы используем толькоn1 числа$ x1, мы должны вычесть конфигурации, используя по крайней мере (n1 + 1) числа$ x1 (что на самом делепути[v - (n1 + 1) x1]). Более того, если мы используем толькоn2 числа$ x2мы должны вычестьпути[v - (n2 + 1) x2] и т. д.

Теперь мы дважды вычитали конфигурации, где по крайней мере (n1 + 1)$ x1 а также (n2 + 1)$ x2 используются, следовательно, мы должны добавитьпути[v - (n1 + 1) x1 - (n2 + 1) x2] и так далее.

В частности, если

N = набор конфигураций, где все монеты используются как можно больше,

искусственный интеллект = набор конфигураций, где хотя бып + 1 числа$ хи используется, для 1 <=i <=m, затем

результат, который мы ищем = |N| - |A1| - |A2| .. - |Am| + |A1 а такжеA2| + |A1 а такжеA3| + ... - |A1 а такжеA2 а такжеA3| .....

Код, который вычисляет количество конфигураций с неограниченным количеством монет, на самом деле проще:

ways[0]=1;
for( int i = 0 ; i < count ; i++){
    for( int j = coins[i] ; j < ways.size() ; j++ ){
        ways[j] += ways[j-coins[i]];
    }
}