Обмен монет с ограниченным количеством монет - PullRequest
Новая
       23

Обмен монет с ограниченным количеством монет

5 голосов
/ 16 ноября 2010

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

Предположим, у вас есть 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}, а затем запустите суммирование Subset на нем, конечно, мы можем получить результат за $ 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;
    }
}

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

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

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

Предположим, путей [v] - способы создания $ v с $ x1 , $ x2, .. $ xm , каждый из которых используется столько раз, сколько необходимо.Теперь, если мы используем только 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 = набор конфигураций, в которых все монеты используются как можно больше,

Ai = набор конфигураций, где используется по крайней мере ni + 1 число $ xi , для 1 <= <em>i <= <em>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]];
    }
}

Ответы [ 2 ]

4 голосов
/ 17 ноября 2010

Давайте предположим, что все ваши ni равны 1.

Пусть ways[j] = number of ways of obtaining sum j.

Вы можете вычислить это примерно так (это то, что вы делаете, но я не знаю, почему вы назвали свою переменную primes). 

ways[0] = 1
for i = 1 to m do
    for j = myLim downto X[i] do
        ways[j] += ways[j - X[i]];

Это означает, что вы используете каждую монету достоинством Xi только один раз.Вы можете добавить еще один цикл, чтобы использовать его как минимум один раз, но не более ni раз: 

ways[0] = 1
for i = 1 to m do
    for times = 1 to n[i] do // use Xi one time, then two times, then three, ..., then ni
        for j = myLim downto times*X[i] do
            ways[j] += ways[j - times*X[i]];

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

0 голосов
/ 16 ноября 2010

Задача называется «Проблема с монетами» и, как известно, является NP-сложной.

Вы можете немного узнать об этом здесь.

...