C++ প্রোগ্রাম সর্বোচ্চ রেট পার্টস সেট খুঁজে বের করতে

ধরুন, একটি প্রস্তুতকারক আছে যে একটি নির্দিষ্ট পণ্যের জন্য নির্দিষ্ট অংশ তৈরি করে। প্রস্তুতকারকের অংশগুলির বিভিন্ন বৈচিত্র রয়েছে এবং তিনটি মানদণ্ডে অংশগুলির একটি নির্দিষ্ট রেটিং রয়েছে৷ n পণ্যের রেটিং অ্যারে 'রেটিং'-এ দেওয়া হয় যেখানে প্রতিটি উপাদান বিন্যাসের (A, B, C) যেখানে A, B, এবং C পণ্যের বিভিন্ন রেটিং মানদণ্ড। এখন, একজন OEM যন্ত্রাংশ প্রস্তুতকারকের কাছ থেকে তাদের তৈরি প্রতিটি পণ্যের জন্য m যন্ত্রাংশ কিনতে চায়। OEM নীচের শর্তগুলি পূরণ করে অংশগুলি বেছে নেয় -

• একই অংশের দুই বা তার বেশি ইউনিট কেনা উচিত নয়।

• অংশগুলির সেট বেছে নিন যাতে V মান সর্বাধিক হয়, যেখানে V =|মানদণ্ডের মোট রেটিং A| + |মানদণ্ডের মোট রেটিং B| + |মাপদণ্ডের মোট রেটিং C|.

OEM যে অংশগুলি বেছে নেয় সেগুলি থেকে আমাদের V এর সর্বাধিক সম্ভাব্য মান খুঁজে বের করতে হবে৷

সুতরাং, যদি ইনপুট হয় n =6, m =4, রেটিং ={{2, 3, 5}, {3, 5, 2}, {4, 8, 5}, {1, 5, 3}, {7, 2, 7}, {4, 3, 6}}, তাহলে আউটপুট হবে 56।

যদি OEM অংশ 1, 3, 5 এবং 6 বেছে নেয়, তাহলে প্রতিটি বিভাগের জন্য মোট রেটিং হল −

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.

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

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

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#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