[C] Ordinamento di una lista in base a somme di valori precedenti

[edoardo1985]

Ciao a tutti,
il mio problema è il seguente: ho una struttura dati dinamica costituita da una lista in cui ogni voce è una coppia di valori (dato che mi interessa solo l'algoritmo e non il codice la si può considerare anche come un array bidimensionale).
Per intenderci, chiamo PESO il primo valore e RESISTENZA il secondo, ad esempio:

PESO     RESISTENZA

80       90
1        91
11       3
3        1

Quello che devo ottenere è una seconda lista, costruita a partire dagli elementi di questa, nella quale il valore RESISTENZA di ogni voce sia >= della somma dei pesi delle voci precedenti.
Qualora non siano utilizzabili tutte le voci della lista (perchè a un certo punto la somma dei pesi supera la resistenza della voce ennesima) è necessario eliminare solo le voci "giuste" e combinare le restanti affinchè la lista sia più lunga possibile.

E' un problema apparentemente semplice ma che presenta diversi casi particolari.
Ci ho ragionato molto sopra ma senza riuscire a concepire nessun algoritmo abbastanza efficace... forse sarebbe opportuno organizzare la lista di partenza in un albero o qualche altra struttura dati prima di sottoporla all'algoritmo.
Voi che ne dite? Mi farebbe piacere sentire anche semplicemente una vostra opinione, per cercare di esplorare altri modi per risolvere il problema.
Grazie!

[bersan]

Questo più che un problema di programmazione è un problema di logica...
La prima cosa che mi viene in mente è:
vecchia lista
80 - 90
1 - 91
11 - 3
3 - 1
inserisco 2 strutture ausiliari per poi cancellarle
0 - 0
0 - 0
ordino la lista in base al seguente criterio:
resistenza + peso - peso_prec1 - peso_prec2
condizione resistenza >= peso_prec1 + peso_prec2
la prima è 3 + 1 - 0 - 0 = 4
riordino
la prima è 11 + 3 - 3 - 0 = 11
riordino
la prima è 1 + 91 - 11 - 3 = 89
rimane 80 + 90 - 3 - 0 = 170
in questo caso non andrebbe eleminato nessun elemento
nuova lista
3 - 1
11 - 3
1 - 91
80 - 90

[bersan]

Dopo qualche ora mi stavo rileggendo…...
Come non detto!
mi sono accorto che è una stupidaggine...
Comunque e un bel rompicapo.

[edoardo1985]

Inizio a credere che nel caso in cui ci sono da eliminare una o più voci bisogna esplorare tutte le possibili combinazioni con n-1 voci, poi con n-2 e così via finchè non si trova una lista possibile... ma in questo modo la complessità dell'algoritmo sale alle stelle!
Spero che qualcuno mi contraddica
Grazie a bersan per il tentativo!

[bersan]

Prova il seguente algoritmo:

considero, per ogni elemento della lista sorgente, l'opportunità di inserirlo nella nuova lista
Se ha la resistenza suficente.
1. Quanta resistenza ha più del necessario?
x = resistenza_elemento - somma_peso_nuova_lista
2. Quanto peso aggiungo alla nuova lista?
y = peso_elemento
inserisco nella lista nuova l'elemento con minore (x+y)
Vado avanti in questo modo finché nessuno degli elementi rimasti ha la resistenza suficente.