Implémentation C/C++ d'un algorithme similaire à la somme de sous-ensembles

Question

Le problème est plus simple que knapsack (ou un type de celui-ci, sans valeurs et seulement des poids positifs). Le problème consiste à vérifier si un nombre peut être une combinaison d'autres. La fonction doit renvoyer true ou false.

Par exemple,

112 et une liste avec { 17, 100, 101 } devrait revenir false, 469 avec la même liste doit retourner true, 35 devrait retourner false, 119 devrait retourner true, etc ...

Edit: le problème de la somme des sous-ensembles serait plus précis pour cela que pour le sac à dos.

Answer 1

Une observation qui vous aidera est que si votre liste est {a, b, c ...} et le nombre que vous voulez tester est x, alors x peut être écrit comme la somme d'une sous-liste uniquement si x ou xa peut être écrit comme une somme de la sous-liste {b, c, ...}. Cela vous permet d'écrire un algorithme récursif très simple pour résoudre le problème.

edit: Voici du code, en tenant compte des commentaires ci-dessous. Non testé donc probablement buggé; et pas nécessairement le plus rapide. Mais pour un petit jeu de données, le travail sera bien fait.

bool is_subset_sum(int x, std::list::const_iterator start, std::list::const_iterator end) 
{ 
    // for a 1-element list {a} we just need to test a|x 
    if (start == end) return (x % *start == 0); 

    // if x is small enough we don't need to bother testing x - a 
    if (x<a) return is_subset_sum (x, start+1, end); 

    // the default case. Note that the shortcut properties of || means the process ends as soon as we get a positive. 
    return (is_subset_sum (x, start+1, end) || is_subset_sum (x-a, start, end)); 
} 

Answer 2

Ceci est un cas particulier du problème Sum sous-ensemble, avec des ensembles qui contiennent seulement un nombre négatif (par exemple, 112 et exprimer {17, 100, 101} comme {-112, 17, 100, 101}). Il y a quelques algorithmes sur la page Wikipedia, http://en.wikipedia.org/wiki/Subset_sum_problem.

Answer 3

Notez que les résultats positifs deviennent plus denses lorsque le nombre demandé augmente. Par exemple, tous les nombres supérieurs à 100^2 peuvent être générés par {17, 100, 101}. Ainsi, l'algorithme optimal peut dépendre du fait que le nombre demandé est beaucoup plus grand que les membres de l'ensemble. Vous pourriez regarder dans la théorie des champs. À tout le moins, vous savez que le résultat est toujours faux si le plus grand diviseur commun de l'ensemble n'est pas dans la requête, et cela peut être vérifié en un temps négligeable.

Answer 4

Si le nombre à atteindre n'est pas trop grand, vous pouvez probablement générer tous les nombres atteignables de l'ensemble qui se trouvent dans la plage [1, N].

Problème: Atteindre N à l'aide des éléments dans la liste L, où N est assez petit pas à vous soucier un vecteur de la taille des éléments de taille N.

algorithme:

• Générez un vecteur V de taille N
• Pour chaque élément l dans la liste L
  • Pour chaque élément accessible v dans V
    • marque tous les éléments v + n*l en V comme accessible