Варианты получения суммы из комбинации заданных слагаемых

Найти все комбинации чисел, дающих заданную сумму. Может понадобиться, например, при "календарном планировании". Каждое число использует однократно. Пытается не прибегнуть к полному перебору и использовать памяти линейно от значения суммы. Проверено в консоли Visual Studio.

#include <stdio.h>
#include <stdlib.h>
 
const int numbers=8; //сколько чисел
int a[numbers]={1,2,3,4,5,9,11,30}; //сами числа
int summa=50; //искомая сумма
int *tmp_num,*tmp_sol; //временный массив чисел, временное решение, массивы будут размерности summa
 
void search (int n, int ni) {
 for (int i=ni; i>0; i--) {
  if (tmp_num[i]==1) {
   int n1=n-i;
   if (n1==0) {
    //очередное решение
    printf ("\n");
    tmp_sol[i]=1;
    for (int j=0; j<=summa; j++) if (tmp_sol[j]==1) printf ("%d ",j);
    tmp_sol[i]=0;
   }
   else if (n1>0) {
    tmp_sol[i]=1; tmp_num[i]=0;
    search(n1,i);
    tmp_sol[i]=0; tmp_num[i]=1;
   }
  }
 }
}
 
void main () {
 tmp_num = (int *)calloc (summa, sizeof(int));
 tmp_sol = (int *)calloc (summa, sizeof(int));
 int i,nNum;
 for (i=0; i<numbers; i++) {
  nNum = a[i];
  if (nNum < summa) tmp_num[nNum]=1;
 }
 search (summa, summa);
 getchar();
}

9 11 30
4 5 11 30
1 3 5 11 30
2 3 4 11 30
2 4 5 9 30
1 2 3 5 9 30

16.12.2013, 19:51 [15446 просмотров]