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

Помощь дата->рейтинг Поиск Почта RSS канал Статистика nickolay.info Домой

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

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

  свежие записипоиск по блогукомментариистатистикао "вирусах" в архивах .zip

Наверх Яндекс.Метрика
© PerS
вход