Maison > Article > développement back-end > Programme C++ pour trouver l'ensemble maximum de pièces évaluées
Supposons qu'il existe un fabricant qui fabrique une pièce spécifique pour un produit spécifique. Les fabricants proposent différentes variantes de pièces qui ont des évaluations spécifiques selon trois normes. Les notes de n produits sont données dans le tableau « notes », où chaque élément est du format (A, B, C), où A, B et C sont des critères de note différents pour le produit. Désormais, un OEM souhaite acheter m pièces requises pour chaque produit auprès d’un fabricant de pièces. L'OEM sélectionne les pièces qui répondent aux conditions suivantes :
Impossible d'acheter deux pièces identiques ou plus.
Sélectionnez un ensemble de pièces qui maximise la valeur V, où V = |note totale de la norme A| + |note totale de la norme B| + |note totale de la norme C|.
Nous devons trouver la valeur maximale possible de V dans la pièce choisie par l'OEM.
Donc, si l'entrée est n = 6, m = 4, notes = {{2, 3, 5}, {3, 5, 2}, {4, 8, 5}, {1, 5, 3} , {7, 2, 7}, {4, 3, 6}}, alors la sortie sera 56.
Si l'OEM sélectionne les pièces 1, 3, 5 et 6, alors la note totale pour chaque catégorie est :
Category A = 2 + 4 + 7 + 4 = 17 Category B = 3 + 8 + 2 + 3 = 16. Category C = 5 + 5 + 7 + 6 = 23 The total value of V is 17 + 16 + 23 = 56.
Pour résoudre ce problème, nous suivrons les étapes suivantes :
N := 100 Define an array arr of size: 9 x N. Define an array ans. for initialize i := 0, when i < n, update (increase i by 1), do: a := first value of ratings[i] b := second value of ratings[i] c := third value of ratings[i] arr[1, i] := a + b + c arr[2, i] := a - b - c arr[3, i] := a + b - c arr[4, i] := a - b + c arr[5, i] := -a + b + c arr[6, i] := -a - b - c arr[7, i] := -a + b - c arr[8, i] := -a - b + c for initialize i := 1, when i <= 8, update (increase i by 1), do: sort the array arr[i] for initialize i := 1, when i <= 8, update (increase i by 1), do: reverse the array arr[i] if m is the same as 0, then: V := 0 Otherwise for initialize j := 1, when j <= 8, update (increase j by 1), do: k := 0 for initialize i := 0, when i < m, update (increase i by 1), do: k := k + arr[j, i] V := maximum of V and k return V
Voyons la mise en œuvre ci-dessous Pour mieux comprendre −
#include <bits/stdc++.h> using namespace std; const int INF = 1e9; const int modval = (int) 1e9 + 7; #define N 100 int solve(int n, int m, vector<tuple<int, int, int>> ratings) { int V, arr[9][N] ; vector<int> ans ; for(int i = 0 ; i < n ; i++) { int a, b, c; tie(a, b, c) = ratings[i]; arr[1][i] = a + b + c ; arr[2][i] = a - b - c ; arr[3][i] = a + b - c ; arr[4][i] = a - b + c ; arr[5][i] = -a + b + c ; arr[6][i] = -a - b - c ; arr[7][i] = -a + b - c ; arr[8][i] = -a - b + c ; } for(int i = 1 ; i <= 8 ; i++) sort(arr[i] , arr[i] + n) ; for(int i = 1 ; i <= 8 ; i++) reverse(arr[i] , arr[i] + n) ; if (m == 0) V = 0 ; else { for (int j = 1; j <= 8; j++) { int k = 0; for (int i = 0; i < m; i++) k += arr[j][i]; V = max(V, k); } } return V; } int main() { int n = 6, m = 4; vector<tuple<int, int, int>> ratings = {{2, 3, 5}, {3, 5, 2}, {4, 8, 5}, {1, 5, 3}, {7, 2, 7}, {4, 3, 6}}; cout<< solve(n, m, ratings); return 0; }
6, 4, {{2, 3, 5}, {3, 5, 2}, {4, 8, 5}, {1, 5, 3}, {7, 2, 7}, {4, 3,6}}
56
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!