le pb du sac à dos est http://en.wikipedia.org/wiki/Fixed-parameter_tractable en ce sens que si on fixe N (nombre voulu dans la notation de ./1) le problème est polynomial, mais si N peut être quelconque il n'y a pas d'algo polynomial à moins que P=NP.
pour la méthode d'onur c'est pas encore ça mais en continuant dans cette direction on devrait retomber sur la programmation dynamique ^^ (qui passe par un tableau au lieu d'appels récursifs pour éviter d'appeler plusieurs fois la fonction avec les mêmes arguments)