Construire une solution optimale à l'emballage des bacs à l'aide d'une «fonction magique» $ phi $

Question

Je prends un cours d'introduction en théorie de la complexité, et comme exercice, on nous a donné le problème suivant.

Considérez le problème d'emballage des bacs, avec des objets de poids positifs (rationnels) $ w = {w_1, w_2, ..., w_n } $ ($ 0 <w_i leq 1 forall i $) qui devraient être placés dans des bacs de Capacité 1. Imaginez que l'on vous donne une "fonction magique" $ phi $ que, étant donné un ensemble $ w $ de poids, vous donne le nombre minimum $ k $ de bacs nécessaires pour emballer les objets correspondants, c'est-à-dire $ phi (W) = k $. Soit $ t (n) $ le temps d'exécution de la mise en œuvre de $ phi (w) $ et construisez un algorithme qui renvoie un emballage optimal et fonctionne en $ o (f (n) + g (n) t (n) ) $ time, où $ f (n) $ et $ g (n) $ sont des polynômes.

Tout d'abord, j'ai essayé de faire des partitions binaires de manière récursive de $ w $ en utilisant ce $ phi (w_1) + phi (w_2) = phi (w) $ pour toute partition $ w_1 cup w_2 = w $ tel que $ w_1 $ et $ w_2 $ séparent des objets qui sont dans différents bacs dans une solution optimale (c'est-à-dire qu'il existe une solution optimale telle qu'aucun poids dans les bacs de partage $ w_1 $ avec n'importe quel poids dans $ w_2 $). Lorsque nous obtenons finalement $ phi (w_j) = 1 $, nous savons que $ w_j $ correspond aux objets dans bin $ j $ dans une solution optimale. Cependant, mes tentatives ici ne donnent que des algorithmes avec $ g (n) $ étant exponentiels dans $ n $.

Deuxièmement, j'ai essayé de construire les bacs un par un, en utilisant cela, pour tous les bacs $ b_j $, $ phi (b_j) + phi (w setminus b_j) = k $. Encore une fois, je n'ai pas encore trouvé d'algorithme où $ g (n) $ est polynomial.

C'est plutôt frustrant, car cela semble être un problème simple. Des suggestions sur le point de commencer?