Costruire una soluzione ottimale all'imballaggio del cestino utilizzando una "funzione magica" $ phi $

Question

Sto seguendo un corso introduttivo nella teoria della complessità e, come esercizio, ci è stato dato il seguente problema.

Considera il problema dell'imballaggio del bidone, con oggetti di pesi positivi (razionali) $ w = {W_1, W_2, ..., w_n } $ ($ 0 <w_i leq 1 forall i $) che dovrebbero essere inseriti nei bin di Capacità 1. Immagina che ti venga data una "funzione magica" $ phi $ che, dato un set $ w $ di pesi, ti dà il numero minimo $ k $ di contenitori necessari per imballare gli oggetti corrispondenti, cioè $ phi (W) = K $. Sia $ t (n) $ denotare il tempo di esecuzione dell'implementazione di $ phi (w) $ e costruire un algoritmo che restituisce un imballaggio ottimale e funziona in $ O (f (n) + g (n) t (n) ) $ tempo, dove $ f (n) $ e $ g (n) $ sono polinomi.

Innanzitutto, ho provato a fare in modo ricorsivo partizioni binarie di $ w $ usando quel $ phi (w_1) + phi (w_2) = phi (w) $ per qualsiasi partizione $ w_1 coppa w_2 = w $ tale che $ w_1 $ e $ w_2 $ separano oggetti che si trovano in bin diversi in una soluzione ottimale (ovvero esiste una soluzione ottimale in modo tale che nessun peso in $ W_1 $ share bin con qualsiasi peso in $ w_2 $). Quando alla fine otteniamo $ phi (w_j) = 1 $, sappiamo che $ w_j $ corrisponde agli oggetti in bin $ j $ in una soluzione ottimale. Tuttavia, i miei tentativi qui producono solo algoritmi con $ g (n) $ esponenziali in $ n $.

In secondo luogo, ho provato a costruire i bidoni uno per uno, usando quello, per tutti i bin $ b_j $, $ phi (b_j) + phi (w setminus b_j) = k $. Ancora una volta, devo ancora trovare un algoritmo in cui $ g (n) $ è polinomio.

È piuttosto frustrante, poiché questo sembra essere un semplice problema. Qualche suggerimento su dove dovrei iniziare?