Algoritmo per trovare la migliore combinazione di dimensioni

Question

Sto cercando un algoritmo per trovare la migliore combinazione di dimensioni per ottenere il risultato desiderato.

Prendere seguente come esempio:

| A | B | C | y | 
|--------|--------|-------|-----| 
| dog | house1 | green | 30 | 
| dog | house1 | blue | 15 | 
| cat | house1 | green | 20 | 
| cat | house2 | red | 5 | 
| turtle | house3 | green | 50 | 

A, B, C sono le dimensioni misurate. y è il risultato misurato.

Se voglio ottenere tutte le combinazioni di dimensioni che svolgono y> = 50 in modo che i risultati saranno:

turtle, house3, green 
turtle, any, green 
turtle, house3, any 
turtle, any, any 
any, house3, green 
any, house3, any 
any, any, green 
any, house1, green 
any, house1, any 

Forse è un problema facile, ma ho cercato di capire una soluzione ottimale in termini di O (n) e non l'ho trovato.

Answer 1

Iniziare con una coda di lavoro contenente (any, any, ..., any), 0. Gli elementi di questa coda saranno coppie costituite da una combinazione e un numero di elementi a sinistra che non possono essere modificati da any (ciò avrà più senso a breve). Fino a quando la coda di lavoro è vuota, rimuovere un elemento da esso e calcolare la somma corrispondente. Se non soddisfa la soglia, quindi scartarla. Altrimenti, segnalalo come una delle combinazioni ricercate. Per ogni any che può essere modificato, per ogni valore in quella colonna, accodare una combinazione consistente di quella corrente con any sostituita da tale valore, con l'indice che blocca tutti i precedenti valori any.

Considerando un limite sensibile all'uscita, questo è all'interno di un fattore polinomiale ottimale (in generale, possono esserci in modo esponenziale molte combinazioni).

In Python 3:

def overthreshold(data, threshold): 
    queue = [(('any',) * len(data[0][0]), 0)] 
    for combination, begin in queue: 
     if sum(row[1] for row in data 
       if all(x in {'any', y} 
         for x, y in zip(combination, row[0]))) < threshold: 
      continue 
     yield combination 
     for i in range(begin, len(combination)): 
      if combination[i] == 'any': 
       queue.extend((combination[:i] + (x,) + combination[i+1:], i + 1) 
          for x in {row[0][i] for row in data}) 


def demo(): 
    data = [ 
     (('dog', 'house1', 'green'), 30), 
     (('dog', 'house1', 'blue'), 15), 
     (('cat', 'house1', 'green'), 20), 
     (('cat', 'house2', 'red'), 5), 
     (('turtle', 'house3', 'green'), 50), 
    ] 
    for combination in overthreshold(data, 50): 
     print(combination)