Maison  >  Article  >  développement back-end  >  Programme C++ pour trouver l'ensemble maximum de pièces évaluées

Programme C++ pour trouver l'ensemble maximum de pièces évaluées

王林
王林avant
2023-09-06 10:33:08918parcourir

C++ 程序以找出最大评级零件集合

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

Exemple

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;
}

input

6, 4, {{2, 3, 5}, {3, 5, 2}, {4, 8, 5}, {1, 5, 3}, {7, 2, 7}, {4, 3,6}}

output

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!

Déclaration:
Cet article est reproduit dans:. en cas de violation, veuillez contacter admin@php.cn Supprimer