Il caso m = 2, y0 = y1 = 1, è un noto problema NP-completo: prendi una serie di numeri positivi (la xi) e dividila in due serie, in modo che la somma degli elementi di quella serie è il più vicino possibile o uguale alla somma degli elementi delle altre serie.
D'altra parte, non devi preoccuparti di questo NP completo, perché il "costo" totale di risolvere questo problema sarebbe il costo del calcolo, oltre al costo di un enorme numero di assi di legno - così come lungo poiché la soluzione non richiede molto tempo rispetto al numero di assi di legno, va bene: -)
D'altra parte, la soluzione potrebbe essere polinomiale nel numero di tavole, con il grado del polinomio in base al numero di macchine - se il tempo di soluzione cresce come un polinomio di grado 20, allora non è molto divertente.
Se il numero di sedie fosse un numero reale e le pile di tavole potessero essere divise, la soluzione sarebbe semplice: sommiamo il numero di assi e il numero totale necessario per ogni sedia, dividiamo entrambe le somme per ottenere il numero di sedie che possono essere costruite (come numeri reali) e dividere di conseguenza le tavole. Prima dovrei calcolare quel numero.
Diciamo che il calcolo ci dice che potremmo costruire ipoteticamente 13.79 sedie. Se questo è il caso, determiniamo se possiamo assegnare pile a macchine in modo tale che ciascuna macchina abbia abbastanza assi per 13 sedie; se questo non funziona, 12 sedie, ecc.
Per scoprire se possiamo costruire k sedie, dobbiamo assegnare mucchi di tavole alle macchine, in modo che almeno le tavole y0 * k siano assegnate alla prima macchina, tavole da y1 * k al secondo e così via. Potresti riuscire a risolverlo in tempi ragionevoli se i numeri non sono troppo grandi; simile all'algoritmo "first fit ordered" per l'imballaggio del cestino:
Per provare a costruire sedie k, calcola il numero di tavole di cui ogni macchina ha bisogno, ordina le macchine con tavole in ordine decrescente. Ordinare le pile per numero di tavole in ordine decrescente. Se ci sono k macchine i cui requisiti possono essere soddisfatti con le pile di k più piccole, allora usare quelle pile e rimuovere le macchine e le pile dall'algoritmo. Calcola quante tavole "di riserva" hai. Se il numero è negativo, prova a costruire sedie k-1.
Per la prima macchina: aggiungi pile complete iniziando dal più grande finché questo non supera il requisito. Quindi aggiungi la pila più piccola che soddisferà il fabbisogno per quella macchina se necessario, ma calcola il numero di assi inutili che hai e, se supera il numero di assi di ricambio, hai fallito. Poi fai lo stesso con la seconda, terza macchina, ecc. Usa il backtracking quando fallisci.