Étant donné les poids et les valeurs de n éléments, nous devons mettre ces éléments dans un sac à dos de capacité W pour obtenir la valeur totale maximale dans le sac à dos.
Dans le problème du sac à dos 0-1 , nous ne sommes pas autorisés à casser des objets. Soit nous prenons tout l'article, soit nous ne le prenons pas.
Entrée :
articles sous forme de paires (valeur, poids)
arr[] = {{60, 10}, {100, 20}, {120, 30}}
Capacité du sac à dos, W = 50 ;
Rendement :
Valeur maximale possible = 240
en prenant des articles de poids 10 et 20 kg et 2/3 fraction
de 30 kg. Le prix total sera donc 60+100+(2/3)(120) = 240
Dans Fractional Knapsack , nous pouvons casser des objets pour maximiser la valeur totale du sac à dos. Ce problème dans lequel nous pouvons casser un objet est aussi appelé le problème du sac à dos fractionnaire.
Saisir : Comme ci-dessus Production : Valeur maximale possible = 240 En prenant des articles complets de 10 kg, 20 kg et 2/3 du dernier article de 30 kg
Une solution de force brute serait d'essayer tous les sous-ensembles possibles avec toutes les fractions différentes, mais cela prendra trop de temps.
Une solution efficace consiste à utiliser l'approche Greedy. L'idée de base de l'approche gourmande est de calculer le rapport valeur/poids pour chaque article et de trier l'article sur la base de ce rapport. Ensuite, prenez l'élément avec le rapport le plus élevé et ajoutez-les jusqu'à ce que nous ne puissions pas ajouter l'élément suivant dans son ensemble et à la fin, ajoutez l'élément suivant autant que possible. Ce qui sera toujours la solution optimale à ce problème.
Algorithme:-
- Calculez le rapport (valeur/poids) pour chaque article.
- Triez tous les éléments dans l'ordre décroissant du ratio.
- Initialiser res =0, curr_cap = given_cap.
- Procédez comme suit pour chaque élément "i" dans l'ordre trié :
tandis que(i.poids){ if(i.weight<=curr_cap) { curr_cap -= i.weight ; res += i.value ; } autre { res += (i.value * (curr_cap/i.weight)); retour res; } }
5. Retour rés.
Un code simple avec notre propre fonction de comparaison peut être écrit comme suit, veuillez voir la fonction de tri de plus près, le troisième argument de la fonction de tri est notre fonction de comparaison qui trie l'élément en fonction du rapport valeur/poids dans un ordre non décroissant.
Après le tri, nous devons boucler sur ces articles et les ajouter à notre sac à dos répondant aux critères mentionnés ci-dessus.
Voici la mise en œuvre de l'idée ci-dessus:
struct Item { int value, weight; // Constructor Item(int value, int weight) { this->value = value; this->weight = weight; }}; // Comparison function to sort Item according to val/weight// ratiobool cmp(struct Item a, struct Item b){ double r1 = (double)a.value / (double)a.weight; double r2 = (double)b.value / (double)b.weight; return r1 > r2;} // Main greedy function to solve problemdouble fractionalKnapsack(int W, struct Item arr[], int n){ // sorting Item on basis of ratio sort(arr, arr + n, cmp); // Uncomment to see new order of Items with their // ratio /* for (int i = 0; i < n; i++) { cout << arr[i].value << " " << arr[i].weight << " : " << ((double)arr[i].value / arr[i].weight) << endl; } */ double finalvalue = 0.0; // Result (value in Knapsack) // Looping through all Items for (int i = 0; i < n; i++) { // If adding Item won't overflow, add it completely if (arr[i].weight <= W) { W -= arr[i].weight; finalvalue += arr[i].value; } // If we can't add current Item, add fractional part // of it else { finalvalue += arr[i].value * ((double)W / (double)arr[i].weight); break; } } // Returning final value return finalvalue;} // Driver codeint main(){ int W = 50; // Weight of knapsack Item arr[] = { { 60, 10 }, { 100, 20 }, { 120, 30 } }; int n = sizeof(arr) / sizeof(arr[0]); // Function call cout << "Maximum value we can obtain = " << fractionalKnapsack(W, arr, n); return 0;}Comme la principale étape de prise de temps est le tri, l'ensemble du problème ne peut être résolu qu'en O(n log n).
Complexité temporelle : O(nlogn)
Espace auxiliaire : O(1)