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