[C] Vettore: trovare il massimo numero di Sottoinsiemi

[novella88]

Dato l'insieme S contenente N numeri generati a caso fra 1 e 1000, determinare il massimo k.
Ovvero: si vuole partizionare l'insieme S in K sottoinsiemi, in modo tale che la somma di tutti gli elementi che appartengono ai sottoinsiemi sia uguale. Bisogna trovare il K massimo.
N.B. Il problema ha sempre soluzione(K =1 )
Ad esempio : se S ={3, 5, 10, 7, 5 }, K risulterà uguale a 3 e i sottoinsiemi :
P1 = { 3,7 };
p2 = {5,5};
p3 = {10};

Io stavo pensando di crearmi un sottovettore e fare la somma e poi compararlo a un altro, e se la somma è uguale incrementare il numero dei sottovettori.
Come devo fare secondo voi ?
Grazie mille

[ascheriit]

Mi pare molto inefficente come approccio, ma anche una volta trovata una soluzione efficente mi pare alquanto difficile dimostrare che e' anche la soluzione migliore...

@hamming_burst:
[ot]Sono in cina con intercultura, in pratica e' da agosto che vivo con una famiglia cinese e studio in una scuola superiore cinese, ma fra meno di un mese devo tornare in Italia e poi a settembre mi tocca di fare 7 esami per evitare di perdere un anno di scuola :S[/ot]

[novella88]

Le somme parziali mi servono, anzi sono importantissime, perché i sottovettori da considerare sono quelli che hanno somme parziali uguali.. Nell'esercizio devo trovare quanti K sottovettori escono a partire da due sottovettori con somme uguali.. Avrò forse capito male la consegna?!! Per quello volevo un confronto..

[apatriarca]

È corretta la tua interpretazione del compito, ma le somme parziali sono tantissime (\(2^N\)) e se devi anche memorizzare il sotto-insieme corrispondente allora devi usare \(N\,2^N\) spazio su disco (e usare un tempo corrispondente). A questo punto dovresti confrontare queste somme parziali e vedere se la loro unione è uguale all'intero array. Anche riuscissi farlo in tempo lineare nell'input la complessità dell'algoritmo sarebbe di almeno \(N\,2^N\) e con ogni probabilità maggiore. È ovvio insomma che è necessario escludere subito il calcolo delle somme inutili se si vuole avere un algoritmo che vedremo terminare in un tempo ragionevole.

[novella88]

Si le somme inutili, cioè quelle già ripetute vanno escluse, potrei fare un ciclo if e vedere se la sequenza è stata già ripetuta non fare la somma, sennò occupa troppo spazio in memoria.

[apatriarca]

Le somme parziali inutili sono molte di più. Per esempio tutte quelle con somma diversa da un divisore della somma totale. Ma l'aspetto veramente importante se si vuole ridurre la complessità è riuscire a considerare solo una parte (la più piccola possibile) di tutti i sottoinsiemi. Se consideri comunque tutti i sottoinsiemi, anche se poi scarti la loro somma parziale, avrai comunque una complessità di tipo \(2^N\).

[novella88]

domani devo mandare il compito al prof,..uff, questa " soluzione" non è tanto bella da vedere, vero?

[apatriarca]

Se hai solo due giorni (immagino che tu lo debba mandare domani sera..), inizia a postare il codice. Bella o brutta che sia la tua soluzione, è più importante che sia una soluzione..

EDIT: Ma volendo trovare una soluzione migliore conviene secondo me cercare di trovare un modo di verificare se un array può essere diviso in \(k\) sottoinsiemi che sommano a \(s\) dove \(k\,s = S\) con \(S\) somma totale.

[novella88]

eh si il problema è di tipo NP-hard..

#include <iostream>
#include <cstdlib>

using namespace std;

// PROTOTIPI
bool diversodaN(int[], int, int);
double sommaelementi(int[], int, int);
void Sommarray2(int [], int N, int &, int );
void riempi(int , int &, int []);
void stampa(int [], int);
//MAIN

int main ()
{
   int a[100],j,N,x,rimasti,nelementi;
   cout<<"Numeri di elementi da introdurre "; cin>>nelementi;
   rimasti=0;
   riempi(nelementi, rimasti, a);
   stampa(a,rimasti);
    cout<<" Introduci elemento da cercare ";
    cin>>N;
    if (diversodaN(a,rimasti,N)==0) cout<<"\n Il numero "<<N<<" e' presente nel vettore "<<endl;
    else
    cout<<"\n Il numero "<<N<<" non e' presente nel vettore "<<endl;
    x=0;
    cout<<"\n La somma degli elementi del vettore e'= "<<sommaelementi(a,rimasti,x)<<endl;
    system("pause");
    int somma=0,conta=0;
    Sommarray2(a,rimasti,somma,conta);
    system("pause");
    return 0;
  }

// DEFINIZIONI

bool diversodaN(int a[], int j, int n )
{
   if  ( j<0)
      return   true;
   else if (a[j]==n)
           return  false;
        else
           return  diversodaN(a,j-1,n);
}
double sommaelementi(int a[], int j,int x)
{
if (x>=j)
        return 0;
else
{
   return  a[x]+(sommaelementi(a,j,x+1));
}
}

void Sommarray2(int vet[], int N, int &somma, int i)
{  // somma elementi vettore mostrando le somme parziali ogni 3
   if (i>N)
   somma=0;
else {
      if (i%3==0) {  cout<<"somma parziale "<<i<<" ="<<somma<<endl;}
   somma=somma+vet[i];
   Sommarray2(vet, N,somma,i+1);}
  }

void riempi(int nelementi, int &rimasti, int Ints[])
{/*Assegnare agli elementi dell’Array di interi Ints, dei numeri
interi positivi compresi nell’intervallo 1..rimasti.
Ogni numero viene dato da tastiera. Il processo di lettura cessa
o quando si introducono tutti i numeri previsti (rimasti) oppure
quando si introduce un numero negativo. Subito dopo si effettua l’assegnazione.
*/
int Temp;
if ((nelementi == 0))
   return;
else
 {
  cin>>Temp;
  if (Temp<=0)
      return;
  else
   {
     Ints[rimasti]=Temp;
     rimasti=rimasti+1;
     riempi(nelementi-1,rimasti,Ints);
    }
   }
}
void stampa(int a[],int N)
{
     for (int i=0;i<N;i++)
     {cout<<i<<"->"<<a[i]<<endl;}
     }

. non l'ho mai fatto veramente, pensavo di avere risolto qualcosa, invece niente..

[novella88]

avete letto il codice?

[apatriarca]

Non ancora, ti ho modificato il post in modo da rendere il codice più leggibile e facile da copiare. In futuro usa il tag code per inserire il codice.

[novella88]

Grazie

[apatriarca]

Alcune osservazioni sul codice:
1. Il tuo codice è in C++ e non in C. Sono due linugaggi differenti..
2. Non mi sembra poi corretto il modo in cui leggi i valori. Nel testo dell'esercizio si parlava infatti di \(N\) numeri generati a caso tra \(1\) e \(1000\), mentre tu li leggi da tastiera e non verifichi che i valori siano nell'intervallo corretto.
3. Il testo dell'esercizio non chiede di trovare un elemento nell'array. Almeno quello che ci hai postato.
4. Per la somma non avrei usato la ricorsione, ma un più semplice ciclo ma mi sembra comunque corretta la funzione.
5. Non mi è chiaro lo scopo di Sommarray2..
Non vedo insomma neanche un abbozzo di soluzione del problema..

[novella88]

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
int addendi[]={3,5,10,7,5};
int indice=0;
int sommaParziale=0;
int primo_addendo=addendi[indice];
int secondo_addendo=addendi[indice];
int i,j;
for(j=0;j<5;j++)

{

    primo_addendo=addendi[indice];

    for(i=indice+1;i<5;i++)
    {
         secondo_addendo=addendi[i];
         sommaParziale = primo_addendo+secondo_addendo;
         printf("somma parziale di %d + %d = %d   \n",primo_addendo,secondo_addendo,sommaParziale);


    }

    puts("========================================================");
    indice++;
}

  system("PAUSE");
  return 0;
}

Ho lasciato stare quel codice e ho scritto questo.
Ora sto considerando solo un certo vettore, poi quando arrivo al risultato, faccio direttamente un vettore random.
Questa soluzione mi calcola bene le somme parziali, come le volevo fare sin dall'inizio, solo che non riesco a visualizzare il primo numero.
cioè, visualizzo 3+5 - 3+10 - 3+7 - 3+5 , poi 5+10 - 5+7 .... ma voglio che prima mi visualizzi anche il numero 3 e 5 da soli.
Voglio che visualizzi 3, 8, 13, 10, 8..... 5, 15, 12 etc.. come posso fare secondo voi?? ho la testa in fumo, anche perché gli indici li faccio partire da zero..

[novella88]

Risposta trovata:

int vec[] = {3,4,5};
	int i, j, size = sizeof(vec)/sizeof(int);

	for(i=0; i<size; i++)
	{
		printf("%d ", vec[i]);
		
		for(j=i+1; j<size; j++)
			printf("%d ", vec[i]+vec[j]);
	}

[vict85]

Stampare a video cose è inutile ai fini della risoluzione del tuo problema. Che algoritmo concreto hai pensato?

[novella88]

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main()
{
   int S[] = {3,5,10,7,5};

	int occ[201] = {0}; // è il vettore massimo dell'elenco delle ricorrenze
	//quindi devo prevedere un vettore di 201 elementi considerando che il massimo numero
	//random che posso generare è 100, perchè posso avere due numeri pari a 100, quindi la somma
	//(100 + 100)+1 =201
	int MAX =0;
	int MAXg = 0;
	int i, j, size = sizeof(S)/sizeof(int);

	for(i=0; i<size; i++)
	{
		printf("%d ", S[i]);
		occ[S[i]]++;

		for(j=i+1; j<size; j++)
		{
			printf("%d ", S[i]+S[j]);

			occ[S[i]+S[j]]++;
		}
	}printf("\n \n");

	//printf("\nOccorrenze\n");
	//for(i=0; i<18; i++)
		//if(occ[i])
			//printf("%d = %d\n", i, occ[i]);


int max = 0;
 for (i=0; i<201; i++)
        if(occ[i]>max)
            max = occ[i];

 printf(" Il numero dei sottoinsiemi K e' : %d", max);



	return 0;

}

Ho pensato questo, anche se non è il massimo, ma almeno funziona..

[apatriarca]

Mi sembra che tu sia partita per la tangente, cercando di risolvere un problema che neanche ti serve.

[novella88]

Come neanche mi serve??

[apatriarca]

Hai idea di come usare quello che hai calcolato? Se la risposta è sì allora non è stato tutto inutile, altrimenti è probabilmente tempo sprecato. Ho l'impressione che tu ti sia messa a calcolare qualcosa che avevi l'impressione ti servisse, senza pensare effettivamente a come usarlo.