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

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

Найти все комбинации чисел, дающих заданную сумму. Может понадобиться, например, при "календарном планировании". Каждое число использует однократно. Пытается не прибегнуть к полному перебору и использовать памяти линейно от значения суммы. Проверено в консоли 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

теги: алгоритм c++

16.12.2013, 19:51; рейтинг: 11634