Нахождение все комбинации ряда для определенной суммы

Question

Array 
A ={1,2,3} 

Для значения Sum = 5
Возможная комбинация

{3,2} , {1,1,1,1,1} , {2,2,1} and all possiable one 

вот мой подход:

int count(int S[], int m, int n) 
{ 
    // m is the size of the array and n is required sum 
    // If n is 0 then there is 1 solution (do not include any coin) 
    if (n == 0) 
     return 1; 

    // If n is less than 0 then no solution exists 
    if (n < 0) 
     return 0; 

    // If there are no coins and n is greater than 0, then no solution exist 
    if (m <=0 && n >= 1) 
     return 0; 

    // count is sum of solutions (i) including S[m-1] (ii) excluding S[m-1] 
    return count(S, m - 1, n) + count(S, m, n-S[m-1]); 
} 

Мой подход Неудобство :: Он должен повторно пересчитывать множество комбинаций снова и снова. Таким образом, значение суммы очень велико, поэтому оно очень медленное.
Я хочу осуществить это с помощью динамического программирования пожалуйста, предоставьте мне объяснения, как я могу хранить вычисленное значение, поэтому я могу использовать его и сократить время моей программы

Answer 1

Для динамического программирования вам нужно обобщать вашу проблему. Пусть S(a, x) - все возможные суммы стоимости x, только с использованием значений от A, начиная с индекса a. Ваша первоначальная проблема: S(0, X).

Поскольку у вас есть дискретная функция с двумя параметрами, вы можете сохранить ее результаты в массиве 2d.

Есть несколько простых случаев: нет решения для a = A.length и X > 0.

Существует набор, содержащий только пустую сумму для X = 0.

Теперь вы должны найти рекурсивную формулу для других случаев и заполнить таблицу таким образом, чтобы индексы, на которые вы зависите, уже были рассчитаны (подсказка: рассмотрим цикл назад).

Answer 2

Я хотел бы сделать это по-другому:

1. генерировать массив монет, чтобы соответствовать сумме

   1. жанрам типа одна монета
      • начать с самого большого
      • добавить их в качестве как вы можете
      • , но сумма должна быть <= то целевая сумма
      • , если целевая сумма достигается сохранить результат
   2. рекурсивный вызов шаг 1 для следующей нижней монеты
      • но помните, последняя монета состояние массива
      • если нет монета = 1, то иногда результат будет недействительным
   3. переход к следующей комбинации
      • восстановления последней монеты массив состояния
      • удалить последнюю монету из него не
      • если есть ни один, чтобы удалить то остановить
      • остальное повторите шаг 2

2. подсчета перестановок/combinantions, если также вопрос о заказе

   • так что верните действительный результат d переставить его по правилам вашей проблемы
   • , чтобы получить больше решений от него
   • это быстрее, чем попробовать все возможности в 1.

пример (для 1.):

coins = { 5,2,1 } 
sum=7 

5 | 2 
5 | -  | 1 1 
- | 2 2 2 | 1 
- | 2 2 | 1 1 1 
- | 2  | 1 1 1 1 1 

• | отделяет рекурсию слоя
• есть один уровень рекурсии по каждому типу монет
• так что вам нужна память для 3-х состояний массива в этом случае (длина зависит от целевой суммы)
• это приемлемо (я видел решения с гораздо более сложной сложностью пространства для этой проблемы)
• для очень больших сумм Я бы использовал RLE для консервирования памяти и ускорив процесс

[edit1] источник C++ код

//--------------------------------------------------------------------------- 
void prn_coins(int *count,int *value,int coins) // just to output solution somewhere 
    { 
    int i; 
    AnsiString s=""; 
    for (i=0;i<coins;i++) 
    s+=AnsiString().sprintf("%ix%i ",count[i],value[i]); 
    Form1->mm_log->Lines->Add(s); 
    } 
//--------------------------------------------------------------------------- 
void get_coins(int *count,int *value,int coins,int sum,int ix=0,int si=0) 
    { 
    if (ix>=coins) return; // exit 
    if (ix==0) // init: 
     { 
     ix=0; // first layer 
     si=0; // no sum in solution for now 
     for (int i=0;i<coins;i++) count[i]=0; // no coins in solution for now 
     } 
    //1. genere actal coint type value[] 
    count[ix]=(sum-si)/value[ix]; // as close to sum as can 
    si+=value[ix]*count[ix];  // update actual sum 
    for(;;) 
     { 
     //2. recursion call 
     if (si==sum) prn_coins(count,value,coins); 
     else get_coins(count,value,coins,sum,ix+1,si); 
     //3. next combination 
     if (count[ix]) { count[ix]--; si-=value[ix]; } 
     else break; 
     } 
    } 
//--------------------------------------------------------------------------- 
void main() 
    { 
    const int _coins=3;    // coin types 
    int value[_coins]={5,2,1};  // coin values (must be in descending order !!!) 
    int count[_coins]={0,0,0};  // coin count in actual solution (RLE) 
    get_coins(count,value,_coins,7); 
    } 
//------------------------------------------------------------------------- 

• этот код взял ~ 3ms на шахте установки HW
• просто изменить функцию prn_coins к вашему форма печати (я использовал записку VCL и AnsiSring)
• в этом коде состояние решения автоматически перезаписывается в предыдущее состояние
• поэтому нет необходимости дальнейшей memoize (иначе это было бы необходимо скопировать кол массив до и после рекурсии)
• Теперь шаг перестановки не будет необходимо, если:
• каждая монета является уникальной? (1 2 5)! = (1 2 5)
• или только тип монеты? (1 1 2 5)! = (1 2 1 5)
• в этом случае просто добавить код перестановки в функции prn_coins ...
• , но это другой вопрос ...

Answer 3

очень простым изменением вашего решения было бы просто добавить «memoization».

Учитывая, что массив S зафиксирован, результат вашей функции зависит только от m и n. Таким образом, вы можете сделать следующее небольшое изменение:

int count(int S[], int m, int n) { 
    ... 
    if (cache[m][n] == -1) { 
     cache[m][n] = count(S, m - 1, n) + count(S, m, n-S[m-1]); 
    } 
    return cache[m][n]; 
} 

Таким образом, вы будете только вычислить результат один раз для каждой отдельной пары значений m и n.

Идея состоит в том, чтобы сохранить 2d-массив, проиндексированный (m, n), все инициализированы до -1 (что означает «еще не вычислено»). Когда вы собираетесь вычислить значение в count, вы сначала проверяете, не вычисленное значение еще, и если это так, вы также сохраняете результат в матрице 2d, чтобы в будущем вы не повторите то же число.