c++ programma combinazioni somme

[Kawa46]

Buona sera a tutti,
mi rivolgo a voi per chiedere aiuto riguardo un programmino che devo scrivere inc++.
Il problema è il seguente: dati n numeri (nel caso specifico una decina), il programa dovrebbe
eseguire tutte le possibili combinazioni di somme e darmi in output quelle che come risultato danno
un numero minore di uno predefinito.
Io ho provato a ragionarci ma ho poca esperienza di programmazione (solo un corso di informatica 1 affrontato anni fa)
,ancora meno di calcolo combinatorio e non sono riuscito ad ottenere ciò che volevo.
Chiederei cortesemente una mano, se non nel listato completo, almeno nella logica da
seguire per venirne a capo.
Grazie dell'attenzione.

[xneo]

Cosa intendi per "tutte le possibili combinazioni di somme"?

L'addizione è una operazione associativa. Quindi puoi avere n! modi per sommare questi n numeri ma il risultato è uguale per tutti i possibili modi.

[Kawa46]

intendo dire che se ad esempio ho a b c vorrei che il programma calcolasse :
a+b
a+c
b+c
a+b+c

Ovvero tutte le somme possibili tra quei tre numeri escludendo la commutazione degli addendi.
Ovviamente con 10 numeri le combinazioni sono molte di più, per questo necessito di un programma.

[hyoukarou]

aiuto riguardo un programmino che devo scrivere
solo un corso di informatica 1 affrontato anni fa

Vi è un motivo per il quale devi scrivere un programma avendo frequentato solo un corso di informatica anni fa?

Buttando giù qualche idea, dato che vi è un numero piccolo di addendi potresti usare una funzione ricorsiva con una specie di induzione sul numero di elementi e per evitare "commutazioni di addendi" potresti ordinarli.

Per fare un esempio concreto, avendo i numeri \(1\), \(2\), \(3\) e \(4\), potresti partire dalle sommatorie di 1 elemento, i.e.

\(1\)
\(2\)
\(3\)
\(4\)

e poi per ognuno di essi(che non supera il massimo) potresti aggiungere addendi più grandi(in modo tale che la somma non superi il massimo, o equivalentemente che l'addendo nuovo non superi il massimo meno la somma degli addendi precedenti):

\(1\):
\(1 + 2\)
\(1 + 3\)
\(1 + 4\)

\(2\):
\(2 + 3\)
\(2 + 4\)

\(3\):
\(3 + 4\)

\(4\):
bang

e così via fino a quando l'insieme dei tuoi elementi non si esaurisce e non superi il massimo valore. Questo non è ovviamente l'unico modo per risolvere il tuo problema, potrebbero essercene migliori, ma per funzionare funziona.

Se sai usare le standard library(cose come questo container) puoi scrivere un codice "guardabile", in caso contrario avrai qualche grana in più.

[onlyReferee]

Data la natura del problema opterei per utilizzare la programmazione dinamica per risolvere lo stesso. Bisogna che cerchi di scomporre il problema in sottoproblemi più semplici fino a raggiungere dei casi base ben noti per cui si può fornire una risposta immediata. Nel nostro caso i casi ben noti sono le somme di due soli addendi.

[vict85]

Che tipo di numeri sono? Perché, in programmazione, dare per scontata associatività e commutatività è pericoloso. Specialmente con i numeri a virgola mobile.

[onlyReferee]

Giusta osservazione, vict85, talvolta diamo sempre per scontato il tipo intero ma...non si sa mai in effetti.

[Kawa46]

Sono tutti numeri interi. Per ora ho provato a cercare qualche info su internet però non ho trovato nulla del genere.
La cosa più utile che ho trovato è stato questo programma che ho adattato al mio problema (non l'ho scritto io, non voglio rubare il merito a chi l'ha fatto):

// Program to print all combination of size r in an array of size n
#include <stdio.h>
void combinationUtil(int arr[], int data[], int start, int end, int index, int r);

// The main function that prints all combinations of size r
// in arr[] of size n. This function mainly uses combinationUtil()
void printCombination(int arr[], int n, int r)
{
// A temporary array to store all combination one by one
int data[r];

// Print all combination using temprary array 'data[]'
combinationUtil(arr, data, 0, n-1, 0, r);
}

/* arr[] ---> Input Array
data[] ---> Temporary array to store current combination
start & end ---> Staring and Ending indexes in arr[]
index ---> Current index in data[]
r ---> Size of a combination to be printed */
void combinationUtil(int arr[], int data[], int start, int end, int index, int r)
{
// Current combination is ready to be printed, print it
if (index == r)
{
for (int j=0; j<r; j++)
printf("%d ", data[j]);
printf("\n");
return;
}

// replace index with all possible elements. The condition
// "end-i+1 >= r-index" makes sure that including one element
// at index will make a combination with remaining elements
// at remaining positions
for (int i=start; i<=end && end-i+1 >= r-index; i++)
{
data[index] = arr[i];
combinationUtil(arr, data, i+1, end, index+1, r);
}
}

// Driver program to test above functions
int main()
{
int arr[] = {445, 438, 338, 363, 398, 590, 324, 296};
int r = 2;
int n = sizeof(arr)/sizeof(arr[0]);
printCombination(arr, n, r);
}

In base al valore di r mi fornisce le combinazioni possibili. Per esempio con r = 2 fornisce:
445 438
445 338
445 363
445 398
445 590
445 324
445 296
438 338
438 363
438 398
438 590
438 324
438 296
338 363
338 398
338 590
338 324
338 296
363 398
363 590
363 324
363 296
398 590
398 324
398 296
590 324
590 296
324 296

Il passo successivo che vorrei ottenere è la somma di questi numeri inserendo anche le combinazioni con r crescenti.

[kobeilprofeta]

Vorrei solo sottolinearti che se inserisci $n$ numeri, avrai $2^n$ possibili "somme"... Non è una cosa proprio "comoda" per il compilatore...