Seleziona il punteggio più alto, ma almeno X per ogni regione

Ho letto la tua domanda un paio di volte, spero di aver capito bene.

Avere i punteggi di ogni regione ordinati in una lista sembra essere una cosa utile da avere.

1. Calcola se ciascuna regione fornisce X punti dati. Se non lo fa, allora può solo contribuire con 0 alla somma complessiva e quindi dovrebbe essere scartato.

2. Da tutte le regioni, calcola il punteggio massimo che possono contribuire con solo X punti dati. Ciò significa, trovare i X punteggi più alti di A, B, ecc.

3. Ora trova la più grande di quelle somme X e aggiungila alla somma complessiva di te aggiungere N-X più elementi alla somma complessiva, che può provenire da due fonti, dovresti scegliere il più grande possibile rispetto alla limitazione imposta da N e aggiungerla alla somma complessiva:

   • Il prossimo più grande elemento di una qualsiasi delle aree già aggiunte. Questo elemento non fa parte degli X elementi più grandi già aggiunti alla somma complessiva. Questo aggiungerà 1 elemento.
   • La prossima più grande somma di X elementi da un'altra area. Questa è la somma dei maggiori elementi di quell'area. Questo aggiungerà X elementi.

Continuo a menzionare il numero di elementi, perché potrebbe essere allettante aggiungere un'area completamente nuova, perché è probabile che aggiunga un numero elevato alla somma complessiva, ma devi stare attento a non andare oltre il limite N.

Questo è difficile. Ovviamente ignori tutte le regioni con meno di X punteggi. Se N < X allora non c'è soluzione, tranne la soluzione banale quando N = 0. Se X ≤ N < 2X quindi devi scegliere tutti i punteggi N dalla stessa regione, che è o banale da fare in modo ottimale o impossibile. Se X = 1, quella non è una restrizione, selezioniamo solo i punteggi più alti.

Ciò che rende difficile è che non usiamo nemmeno necessariamente la regione in cui i punteggi X più alti sommati sono più alti. Diciamo X = 3 e N = 8 e punteggi (1001,1000,1000), (1000,1000,1000,1000), (1000,1000,1000,1000), (0,0,0,0,0 ). Se usiamo 3 punteggi dalla prima regione, dobbiamo usare i punteggi dell'ultima regione, che è molto peggio che usare la seconda e la terza regione.

Una soluzione ottimale sceglierà k regioni, dove k x ≤ N e il numero totale di punteggi in queste regioni è ≥ N, scegli i punteggi X più alti da ciascuna regione, quindi scegli il rimanente N-k x punteggi da quelle regioni.

Potrebbe essere necessario effettuare una ricerca esaustiva, escludendo il maggior numero possibile di casi. Ci sono molte cose per ridurre il numero di casi in una ricerca esauriente.

Diciamo che Regione A > Regione B se la somma dei punteggi X più alti è uguale o superiore e se B ha k punteggi per k > X poi A ha anche k punteggi, e la somma dei punteggi k più alti è uguale o superiore, e se tutti i punteggi sono gli stessi allora A deve essere il primo nella lista delle regioni. Con questa definizione, non è necessario esaminare le soluzioni che contengono B, ma non A. A seconda dei dati, ciò potrebbe escludere molte possibilità.

Se la regione R è inferiore a diverse regioni con un totale di n punteggi, possiamo ignorare completamente la regione R. La regione R può essere "meno di" due regioni combinate: se qualunque punteggio prendiamo dalla regione R, possiamo uguagliare o meglio con i punteggi da A e B secondo le regole, quindi possiamo ignorare R se nessuno dei due A e B è parte della soluzione.

Sono d'accordo con il suggerimento di @ null di avere elenchi ordinati per ogni regione.

Quindi, come il mio approccio a questo problema sarebbe:

1. Crea distinti elenchi ordinati per ogni regione in modo che vengano ordinati in base ai loro punteggi e si disponga di un elenco diverso per ogni regione. Ovviamente ci sono diversi modi per farlo, in che modo dovresti usare dipende dal tuo set di dati.
   Ad esempio, alla fine, potresti avere qualcosa di simile :

   regionA = [(9,A),(6,A),(4,A)]
   regionB = [(7,B),(6,B),(5,B),(4,B)]
   regionC = [(15,C),(4,C)]
   

2. Dopo aver creato gli elenchi ordinati separati per ciascuna regione. Controlla se una lista è più corta di X, in tal caso scarta questa lista.
   Quindi per l'esempio sopra, diciamo se X = 3, dovremmo eliminare l'areaC.
3. Ora dovresti avere separato gli elenchi ordinati per le regioni che hanno più di X elementi. Dato che sono già ordinati in base ai punteggi, ora tutto ciò che devi fare è; prendi semplicemente le somme dei punteggi degli elementi N più alti / primi (supponendo che scendano in ordine decrescente) da ciascuna lista e confrontali. La somma più alta che hai ottenuto è la selezione che dovresti scegliere.
   Esempio continua; prendiamo N = 3. Siamo rimasti con regione A e regione ora sinistra. Per il quale le prime somme di 3 elementi sarebbero sumA = 19, sumB = 18 . Nel qual caso dovremmo scegliere la regione A.

Ho usato idee dalla risposta di Gnasher per scrivere uno script Python. È non documentato e difficile da leggere. Ma dal momento che questo problema sembra abbastanza standard e tuttavia difficile da risolvere, sto pubblicando questo script per i disperati che potrebbero incontrare questo problema. Lo script manca una ottimizzazione per la ricerca esauriente. Assume invece un ordinamento lineare semplice A<B<C<... di regioni nella variabile possible_group_subsets .

from pprint import pprint
import random
from collections import Counter
import itertools as itoo
from operator import itemgetter
import cytoolz as tz


def merge_groupby(*datas, key=None):
    """
    datas should be sorted iterables

    returns [(key, [dat1, dat2, ...])] where key is ascending and dat* are data elements with that key
    key(dat) should be strictly increasing (not repeats) within each stream
    data will be iterated in data_iters as iterators
    it only needs to store len(datas) values

    Example:
    merge_groupby([1,2,3],[2]) -> [(1,[1]), (2,[2,2]), (3, [3])]
    """
    STOP_OBJ = object()
    if key is None:
        key = lambda x: x

    data_iters = [iter(d) for d in datas]
    head_values = []
    for d in data_iters:
        head_val = next(d, STOP_OBJ)
        head_key = key(head_val) if head_val is not STOP_OBJ else STOP_OBJ
        head_values.append((head_key, head_val))

    while not all(h[0] is STOP_OBJ for h in head_values):
        # print(head_values)
        min_key = min(filter(lambda x: x is not STOP_OBJ, tz.pluck(0, head_values)))
        result = []
        result_i = []
        for i in range(len(head_values)):
            head_key, head_val = head_values[i]
            if head_key == min_key:
                result.append(head_val)
                result_i.append(i)
        yield (min_key, result, result_i)

        # this needs to be at the end, so that the result is return before the next
        # element is read
        # otherwise groupby values groups might be automatically consumed/deleted if
        # the group advances
        for i in range(len(head_values)):
            head_key, head_val = head_values[i]
            if head_key == min_key:
                new_head_val = next(data_iters[i], STOP_OBJ)
                assert new_head_val is STOP_OBJ or new_head_val > head_val
                new_head_key = key(new_head_val) if new_head_val is not STOP_OBJ else STOP_OBJ
                head_values[i] = (new_head_key, new_head_val)


def pick(data, minsize):
    sum_groups_minsize = Counter()
    count_groups = Counter()
    for score, group, info in data:  # make one pass with sum and count
        if count_groups[group] < minsize:
            sum_groups_minsize[group] += score
        count_groups[group] += 1

    for group in list(sum_groups_minsize.keys()):  # remove small groups
        if count_groups[group] < minsize:
            del sum_groups_minsize[group]

    def group_select(groups):
        sum_score = sum(sum_groups_minsize[g] for g in groups)
        chosen_cnt = len(groups) * minsize
        seen_counter = Counter()
        for score, group, _info in data:
            if group not in groups:
                continue
            seen_counter[group] += 1
            if seen_counter[group] > minsize:
                sum_score += score
                chosen_cnt += 1
            yield chosen_cnt, sum_score, {g: max(seen_counter[g], minsize) for g in groups}

    # determine allowed group subsets
    sum_minsize_top = [group for group, summer in sorted(sum_groups_minsize.items(), key=lambda x: x[1], reverse=True)]
    possible_group_subsets = [sum_minsize_top[:num_groups_used] for
                              num_groups_used in range(1, len(sum_minsize_top) + 1)]

    # run algorithm
    group_iters0 = [group_select(group_subset) for group_subset in possible_group_subsets]
    group_iters1 = [itoo.groupby(g, key=itemgetter(0, 1)) for g in group_iters0]
    for chosen_cnt, head_group_iters, _head_group_idx in merge_groupby(*group_iters1, key=lambda x: x[0][0]):
        (best_group, best_score), best_grouper = max(head_group_iters, key=lambda x: x[0][1])
        _, sum_score, group_counts = list(best_grouper)[0]  # for tie scores just pick the first option
        yield (chosen_cnt, sum_score, group_counts)

res = list(pick(dat, minsize))