| dbo:abstract
|
- En algorithmique, le problème du sac à dos, parfois noté (KP) (de l'anglais Knapsack Problem) est un problème d'optimisation combinatoire.Il modélise une situation analogue au remplissage d'un sac à dos, ne pouvant supporter plus d'un certain poids, avec tout ou partie d'un ensemble donné d'objets ayant chacun un poids et une valeur. Les objets mis dans le sac à dos doivent maximiser la valeur totale, sans dépasser le poids maximum. (fr)
- En algorithmique, le problème du sac à dos, parfois noté (KP) (de l'anglais Knapsack Problem) est un problème d'optimisation combinatoire.Il modélise une situation analogue au remplissage d'un sac à dos, ne pouvant supporter plus d'un certain poids, avec tout ou partie d'un ensemble donné d'objets ayant chacun un poids et une valeur. Les objets mis dans le sac à dos doivent maximiser la valeur totale, sans dépasser le poids maximum. (fr)
|
| prop-fr:contenu
|
- La preuve de NP-complétude se fait en utilisant le problème de sac à dos sous la forme d'un problème de décision. Elle se fait en deux étapes, premièrement vérifier que appartient à la classe NP et, deuxièmement, montrer que est NP-difficile.
On utilisera, pour la preuve d'appartenance à NP-difficile, la version somme de sous-ensembles , notée , une version particulière du sac à dos dans laquelle le profit d'un objet est égal à son poids. Si cette version particulière est NP-difficile, alors dans toute sa généralité l'est aussi.
Le problème peut-être obtenu à partir du problème de sac à dos ci-dessus en posant . En posant , on obtient :
Trouver tel que
*
*
;Appartenance à NP
Premièrement, on doit prouver que appartient à la classe NP, c’est-à-dire qu'il existe un algorithme polynomial qui, étant donné une solution au problème, peut vérifier que cette solution soit bonne. Pour vérifier une solution, il suffit de calculer la somme des poids des objets choisis et de la comparer avec , ainsi que la somme de leurs valeurs, à comparer avec . Le tout est évidemment polynomial.
;Appartenance à NP-difficile
Il s'agit maintenant de montrer que est un problème NP-difficile en transformant le problème de la couverture exacte en un problème . Le problème s'exprime ainsi :
Soit un ensemble d'éléments et un ensemble de sous-ensembles de . Existe-t-il un sous-ensemble de tel que :
* : tous les éléments de y soient ;
* : chaque élément de n'est que dans un seul des sous-ensembles choisis.
Le problème est NP-complet. En montrant que toute instance de peut être transformée polynomialement en une instance de alors on aura prouvé que appartient à la classe des problèmes NP-difficiles.
Soit une instance quelconque de . Sans perdre de généralité, nous considérerons que . Nous noterons :
: l'état de l'ensemble ;
: l'appartenance de la valeur à l'ensemble .
Soit . Les variables du problème sont les du problème . Nous définissons leur poids de la façon suivante :
:.
On définit la capacité par
:.
Le poids de l'objet est une somme de puissances de et apparaît dans si et seulement si . Par conséquent, il y a une correspondance de un à un entre la solution du problème construit et l'instance de . Chaque valeur se calcule en et la valeur de se calcule en . La transformation a donc une complexité temporelle en . (fr)
- La preuve de NP-complétude se fait en utilisant le problème de sac à dos sous la forme d'un problème de décision. Elle se fait en deux étapes, premièrement vérifier que appartient à la classe NP et, deuxièmement, montrer que est NP-difficile.
On utilisera, pour la preuve d'appartenance à NP-difficile, la version somme de sous-ensembles , notée , une version particulière du sac à dos dans laquelle le profit d'un objet est égal à son poids. Si cette version particulière est NP-difficile, alors dans toute sa généralité l'est aussi.
Le problème peut-être obtenu à partir du problème de sac à dos ci-dessus en posant . En posant , on obtient :
Trouver tel que
*
*
;Appartenance à NP
Premièrement, on doit prouver que appartient à la classe NP, c’est-à-dire qu'il existe un algorithme polynomial qui, étant donné une solution au problème, peut vérifier que cette solution soit bonne. Pour vérifier une solution, il suffit de calculer la somme des poids des objets choisis et de la comparer avec , ainsi que la somme de leurs valeurs, à comparer avec . Le tout est évidemment polynomial.
;Appartenance à NP-difficile
Il s'agit maintenant de montrer que est un problème NP-difficile en transformant le problème de la couverture exacte en un problème . Le problème s'exprime ainsi :
Soit un ensemble d'éléments et un ensemble de sous-ensembles de . Existe-t-il un sous-ensemble de tel que :
* : tous les éléments de y soient ;
* : chaque élément de n'est que dans un seul des sous-ensembles choisis.
Le problème est NP-complet. En montrant que toute instance de peut être transformée polynomialement en une instance de alors on aura prouvé que appartient à la classe des problèmes NP-difficiles.
Soit une instance quelconque de . Sans perdre de généralité, nous considérerons que . Nous noterons :
: l'état de l'ensemble ;
: l'appartenance de la valeur à l'ensemble .
Soit . Les variables du problème sont les du problème . Nous définissons leur poids de la façon suivante :
:.
On définit la capacité par
:.
Le poids de l'objet est une somme de puissances de et apparaît dans si et seulement si . Par conséquent, il y a une correspondance de un à un entre la solution du problème construit et l'instance de . Chaque valeur se calcule en et la valeur de se calcule en . La transformation a donc une complexité temporelle en . (fr)
|
| rdfs:comment
|
- En algorithmique, le problème du sac à dos, parfois noté (KP) (de l'anglais Knapsack Problem) est un problème d'optimisation combinatoire.Il modélise une situation analogue au remplissage d'un sac à dos, ne pouvant supporter plus d'un certain poids, avec tout ou partie d'un ensemble donné d'objets ayant chacun un poids et une valeur. Les objets mis dans le sac à dos doivent maximiser la valeur totale, sans dépasser le poids maximum. (fr)
- En algorithmique, le problème du sac à dos, parfois noté (KP) (de l'anglais Knapsack Problem) est un problème d'optimisation combinatoire.Il modélise une situation analogue au remplissage d'un sac à dos, ne pouvant supporter plus d'un certain poids, avec tout ou partie d'un ensemble donné d'objets ayant chacun un poids et une valeur. Les objets mis dans le sac à dos doivent maximiser la valeur totale, sans dépasser le poids maximum. (fr)
|
