Le problème du sac à dos fractionnaire en C++ fait référence à l'identification d'un moyen de remplir un sac avec des articles d'un poids et d'un profit donnés de telle manière que le sac contienne la valeur maximale sans dépasser la limite maximale.
Comment résoudre le problème du sac à dos fractionnaire en C++
Étant donné un ensemble d'articles, chacun avec un poids et un profit donnés, déterminez chaque nombre d'articles dans une combinaison telle que le poids total des articles soit inférieur à la limite maximale du sac, mais la valeur doit être maintenue aussi grande que possible.
Algorithme pour implémenter le problème du sac à dos fractionnaire
Le fonctionnement de l’algorithme Knapsack peut être compris à travers les points suivants :
- Prenez deux tableaux de poids et de profit.
- Définissez la valeur de sac maximale sur W.
- Déterminez la densité en prenant le rapport des deux paramètres.
- Triez les éléments par ordre décroissant de densité.
- Additionnez les valeurs jusqu'à ce qu'elles soient <=W.
L'approche gourmande pour résoudre le problème du sac à dos fractionnaire
L’approche gourmande vise à faire des choix idéaux à chaque étape, conduisant à la solution idéale à la fin. Il résout les problèmes étape par étape menant à des conclusions au lieu de conclure uniquement aux résultats à la fin. Il s'agit d'un code source pour implémenter une solution au problème du sac à dos fractionnaire en C++ :
#include
en utilisant espace de noms norme ;
structurer Objet {
int valeur, poids ;
Objet ( int valeur, int poids )
: valeur ( valeur ) , poids ( poids )
{
}
} ;
bouffon cmp ( structurer Objet x, structurer Objet y )
{
double A1 = ( double ) X. valeur / X. poids ;
double A2 = ( double ) et. valeur / et. poids ;
retour A1 > A2 ;
}
double fractionnaireKnapsack ( structurer Objet arr [ ] ,
int DANS, int taille )
{
trier ( arr, arr + taille, cmp ) ;
int poids cur = 0 ;
double valeur finale = 0,0 ;
pour ( int je = 0 ; je < taille ; je ++ ) {
si ( poids cur + arr [ je ] . poids <= DANS ) {
poids cur + = arr [ je ] . poids ;
valeur finale + = arr [ je ] . valeur ;
}
autre {
int rester = DANS - poids cur ;
valeur finale + = arr [ je ] . valeur
* ( ( double ) rester
/ arr [ je ] . poids ) ;
casser ;
}
}
retour valeur finale ;
}
int dans = 60 ;
Objet arr [ ] = { { 100 , vingt } ,
{ 380 , 40 } ,
{ 140 , dix } ,
{ 180 , 30 } } ;
int taille = taille de ( arr ) / taille de ( arr [ 0 ] ) ;
cout << 'Bénéfice maximum = '
<< fractionnaireKnapsack ( arr, v, taille ) ;
retour 0 ;
}
Dans ce code, une structure d'objet est définie dans laquelle sont stockées des valeurs de poids et de profit. Le bool cmp() est utilisé pour faire une comparaison entre deux objets sur la base du rapport poids/valeur de deux objets. Le tableau est organisé par ordre décroissant et la valeur continue de s'ajouter jusqu'à atteindre le maximum. Si la valeur actuelle est admissible et dans la limite, elle est ajoutée, sinon son rapport réduit est ajouté au sac. L'ampleur du poids et de la valeur est saisie dans le code principal et le profit maximum est imprimé sur la sortie.
Le bénéfice maximum stocké dans la collation est de 580.
Conclusion
Le problème du sac à dos fractionnaire en C++ fait référence à l'identification d'un moyen de remplir un sac avec des articles d'un poids et d'un profit donnés de telle manière que le sac contienne la valeur maximale sans dépasser la limite maximale. Ceci peut être réalisé grâce à l’approche gourmande qui vise à faire des choix idéaux à chaque étape, conduisant à la solution idéale à la fin.