01Programmation dynamique du problème du sac à dos

L'idée de base de la programmation dynamique :

Les algorithmes de programmation dynamique sont généralement utilisés pour résoudre des problèmes avec certaines propriétés optimales, c'est-à-dire ce que nous appelons habituellement lesdites propriétés optimales de la sous-structure.

L'algorithme de programmation dynamique est similaire à la méthode diviser pour régner. Son idée de base est de décomposer le problème à résoudre en plusieurs sous-problèmes, de résoudre d'abord les sous-problèmes, puis d'obtenir la solution. le problème initial à partir des solutions de ces sous-problèmes. La plus grande différence par rapport à la méthode diviser pour régner est que pour les problèmes pouvant être résolus par programmation dynamique, les sous-problèmes obtenus après décomposition ne sont souvent pas indépendants les uns des autres, c'est-à-dire la solution de la sous-étape suivante est basé sur la solution de la sous-étape précédente.

Si la méthode diviser pour mieux régner est utilisée pour résoudre ce type de problème, il y aura trop de sous-problèmes décomposés et certains sous-problèmes seront recalculés plusieurs fois. Si nous pouvons enregistrer les réponses aux sous-problèmes résolus et trouver les réponses en cas de besoin, nous pouvons éviter de nombreux calculs répétés et gagner du temps. Nous pouvons utiliser un tableau pour enregistrer les réponses à tous les sous-problèmes résolus. Que le sous-problème soit utilisé ultérieurement ou non, tant qu'il est calculé, ses résultats sont renseignés dans le tableau.

Description du problème :

Étant donné N articles et un sac à dos. Le poids de l'article i est Wi, sa valeur est Vi et la capacité du sac à dos est C. Comment dois-je choisir les objets à mettre dans le sac à dos afin que la valeur totale des objets transférés dans le sac à dos soit maximisée ? ?

Lors de la sélection des articles, il n'y a que deux options pour chaque article, à savoir le mettre dans le sac à dos ou ne pas le mettre dans le sac à dos. Vous ne pouvez pas charger l'élément i plusieurs fois, ni charger seulement une partie de l'élément. Par conséquent, ce problème est appelé problème du sac à dos 0-1.

Analyse du problème : Laissons V(i,j) représenter que la capacité qui peut être chargée dans les premiers i(1<=i<=n) est j(1<= j< ; = la valeur maximale des éléments dans le sac à dos de C), la fonction de programmation dynamique suivante peut être obtenue :

(1)   V(i,0)=V(0,j)=0 

(2)   (a)  V(i,j)=V(i-1,j)    j<wi  

      (b)  V(i,j)=max{V(i-1,j) ,V(i-1,j-wi)+vi) }   j>wi

(1) L'équation (1) montre que : si le poids du i-ème L'élément est supérieur à la capacité du sac à dos, alors la valeur maximale obtenue par l'élément i est la même que la valeur maximale obtenue par i-1 éléments avant le chargement, c'est-à-dire que l'élément i ne peut pas être chargé dans le sac à dos.

L'équation (2) montre : Si le poids du i-ème article est inférieur à la capacité du sac à dos, il y aura les deux situations suivantes : (a) Si le i-ème article n'est pas chargé dans le sac à dos, alors la valeur des objets dans le sac à dos Elle est égale à la valeur obtenue en mettant les i-1 premiers objets dans un sac à dos de capacité j. (b) Si le i-ème article est mis dans le sac à dos, la valeur de l'article du sac à dos est égale à la valeur du i-1ème article dans le sac à dos avec une capacité j-wi plus la valeur du i-ème article vi ; Évidemment, prenez Celui qui a la plus grande valeur est la solution optimale pour charger les premiers i articles dans un sac à dos d'une capacité de j.

Tutoriel recommandé : Tutoriel PHP

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!