Hej! Vill kolla med er om ni har någon koll på hur man bäst löser följande:

Jag har en lista med 2 kolumner:
<code>
A B
155 252
158 235
159 1
190 1
216 5
234 67
osv..
</code>

Listan är ganska lång och den ändrar sig från dag till dag.
Jag skulle behöva fram hur jag ska gruppera dem enligt följande:
1) I en grupp får skillnaden mellan högsta och lägsta A vara max 100
2) Summan av B i en grupp måste vara mer än 200
3) De ska grupperas så summan av B i de som inte kunnat grupperas är så liten som möjligt.

Hoppas att ni hänger med.

Tacksam för all hjälp!

Det är en variant av ett ganska allmänt problem, som (om jag inte minns fel) är NP-komplett, dvs "jävligt svårt".

Utan att veta speciellt mycket om ditt speciella fall, kan du göra någon slags heuristisk ide:

Börja med att välja lägsta A; leta utifrån det ut den största möjliga grupp du kan komma åt. Om den uppfyller villkoren är det bra.

Ta sen högsta A, leta på samma sätt.

Sen går du igenom hela listan uppifrån och ner, och försöker ta så mycket du kan varje gång utan att tränga in på någon annan grupp. Eller möjligtvis alternera mellan högsta och lägsta tillgängliga A.

Jo, jag insåg att det har en ganska stor likhet med "best fit"-problemet, men eftersom jag inte har någon övre gräns på B (den skall bara vara mer än 200 i en grupp) borde inte denna problematiken uppstå. (om det u är denna problematik som du syftar på)

Ditt lösningsförslag är ungefär det jag kom att tänka på själv igår kväll. Ska sätta mig under dagen och spåna lite.. =)