Migliori N combinazioni da due insiemi ordinati
Salve a tutti,
sono nuovo (è la prima volta che scrivo), ma leggo il forum con una certa frequenza già da un po' di tempo, molto utile
Non so se questo thread fosse da postare qui o nella sezione di Probabilità statistica, ma non è vero e proprio calcolo combinatorio.
Il mio problema è il seguente: ho due insiemi di elementi che hanno un valore, per semplicità diciamo due insiemi di numeri, insiemi A e B. Questi due insiemi sono ordinati, quindi so già quale sia il valore più piccolo di A, il secondo ecc. Per chiarezza chiamiamo questi elementi A1, A2, ... Am. Lo stesso per l'insieme B, conosoco già il suo ordinamento B1, B2, ... Bk.
Ora da questi due insiemi io voglio creare combinazioni che contengono un valore di A e un valore di B, ad esempio (A1, B2). Il valore di una data combinazione è la somma dell'elemento di A e l'elemento di B (ad esempio combinazione (A3,B1) ha come valore A3+B1).
Mi serve ora un algoritmo, che dati i due insiemi ordinati A e B, mi crei le migliori N combinazioni create come spiegato. Milgiori nel senso le N combinazioni con valore più piccolo (o più grande).
L'algoritmo non può creare due volte la stessa combinazione (ad esempio non può creare due volte la combinazione (A4,B7), una volta che questa è stata creata, non può più essere riutilizzata), ma può riutilizzare elementi già utilizzati in altre combinazioni, ad esempio potrebbe generare le combinazioni (A1,B1),(A1,B2),(A1,B3),(A2,B1) ecc...
Lo scopo dell'algoritmo sarebbe quello di sfruttare il fatto che i due insiemi A e B sono già ordinati e quindi di non dover provare tutte le possibili combinazioni.
Non so se esiste un algoritmo del genere... Sicuramente la prima combinazione che deve essere creata (la migliore), sarà sempre (A1,B1), mentre la seconda sarà (A1,B2) se (A2-A1)>(B2-B1) o (A2,B1) se (A2-A1)<(B2-B1), ma poi? Vi è comunque un'esplosione combinatoria e si va a finire che si "provano" comunque tutte le combinazioni possibili.
Un altro approccio potrebbe essere quello di "unire" i due insiemi A e B e ordinarli,dopodiché scorrere gli elementi finché non se ne trova il primo del tipo A e il primo del tipo B, ma anche così non vedo bene come si potrebbe generalizzare.
Qualche idea? Un approccio tipo dynamic programming potrebbe essere utile? In che modo?
L'idea sarebbe poi quello che l'algoritmo funzioni con J insiemi (ad esempio non solo A e B, ma anche C, D ecc.), ma già una soluzione con 2 non sarebbe male
Vi ringrazio.
Lama
sono nuovo (è la prima volta che scrivo), ma leggo il forum con una certa frequenza già da un po' di tempo, molto utile
Non so se questo thread fosse da postare qui o nella sezione di Probabilità statistica, ma non è vero e proprio calcolo combinatorio.
Il mio problema è il seguente: ho due insiemi di elementi che hanno un valore, per semplicità diciamo due insiemi di numeri, insiemi A e B. Questi due insiemi sono ordinati, quindi so già quale sia il valore più piccolo di A, il secondo ecc. Per chiarezza chiamiamo questi elementi A1, A2, ... Am. Lo stesso per l'insieme B, conosoco già il suo ordinamento B1, B2, ... Bk.
Ora da questi due insiemi io voglio creare combinazioni che contengono un valore di A e un valore di B, ad esempio (A1, B2). Il valore di una data combinazione è la somma dell'elemento di A e l'elemento di B (ad esempio combinazione (A3,B1) ha come valore A3+B1).
Mi serve ora un algoritmo, che dati i due insiemi ordinati A e B, mi crei le migliori N combinazioni create come spiegato. Milgiori nel senso le N combinazioni con valore più piccolo (o più grande).
L'algoritmo non può creare due volte la stessa combinazione (ad esempio non può creare due volte la combinazione (A4,B7), una volta che questa è stata creata, non può più essere riutilizzata), ma può riutilizzare elementi già utilizzati in altre combinazioni, ad esempio potrebbe generare le combinazioni (A1,B1),(A1,B2),(A1,B3),(A2,B1) ecc...
Lo scopo dell'algoritmo sarebbe quello di sfruttare il fatto che i due insiemi A e B sono già ordinati e quindi di non dover provare tutte le possibili combinazioni.
Non so se esiste un algoritmo del genere... Sicuramente la prima combinazione che deve essere creata (la migliore), sarà sempre (A1,B1), mentre la seconda sarà (A1,B2) se (A2-A1)>(B2-B1) o (A2,B1) se (A2-A1)<(B2-B1), ma poi? Vi è comunque un'esplosione combinatoria e si va a finire che si "provano" comunque tutte le combinazioni possibili.
Un altro approccio potrebbe essere quello di "unire" i due insiemi A e B e ordinarli,dopodiché scorrere gli elementi finché non se ne trova il primo del tipo A e il primo del tipo B, ma anche così non vedo bene come si potrebbe generalizzare.
Qualche idea? Un approccio tipo dynamic programming potrebbe essere utile? In che modo?
L'idea sarebbe poi quello che l'algoritmo funzioni con J insiemi (ad esempio non solo A e B, ma anche C, D ecc.), ma già una soluzione con 2 non sarebbe male
Vi ringrazio.
Lama
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo