Chương trình C ++ để tìm ra các bộ phận được xếp hạng tối đa

Giả sử, có một nhà sản xuất sản xuất các bộ phận cụ thể cho một sản phẩm cụ thể. Nhà sản xuất có n biến thể khác nhau của các bộ phận, và các bộ phận có xếp hạng cụ thể trên ba tiêu chí. Xếp hạng của n sản phẩm được đưa ra trong mảng 'xếp hạng' trong đó mỗi phần tử có định dạng (A, B, C) trong đó A, B và C là các tiêu chí xếp hạng khác nhau của sản phẩm. Bây giờ, một OEM muốn mua m bộ phận cho mỗi sản phẩm mà họ tạo ra từ nhà sản xuất bộ phận đó. OEM chọn các bộ phận đáp ứng các điều kiện dưới đây -

• Không nên mua hai hoặc nhiều đơn vị của cùng một bộ phận.

• Chọn tập hợp các bộ phận sao cho giá trị V là cực đại, trong đó V =| tổng đánh giá của tiêu chí A | + | tổng xếp hạng của tiêu chí B | + | tổng xếp hạng của tiêu chí C |.

Chúng tôi phải tìm giá trị lớn nhất có thể có của V từ các bộ phận mà OEM chọn.

Vì vậy, nếu đầu vào là n =6, m =4, xếp hạng ={{2, 3, 5}, {3, 5, 2}, {4, 8, 5}, {1, 5, 3}, {7, 2, 7}, {4, 3, 6}}, thì đầu ra sẽ là 56.

Nếu OEM chọn các phần 1, 3, 5 và 6, thì tổng xếp hạng cho mỗi danh mục là -

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.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

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

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

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

Đầu ra

56