মান লিজিয়ে, একটি ম্যানুফ্যাকচারার একটি নির্দিষ্ট পণ্যের জন্য নির্দিষ্ট পার্টস তৈরি করে। ম্যানুফ্যাকচারারের n টি ভিন্ন ভেরিয়েশন পার্টস আছে, এবং পার্টসগুলো তিনটি মাপদণ্ডে রেট করা হয়। n টি পণ্যের রেটিং 'ratings' অ্যারেতে দেওয়া আছে যেখানে প্রতিটি উপাদান হলো (A, B, C) যেখানে A, B, এবং C হলো পণ্যের ভিন্ন রেটিং মাপদণ্ড। এখন একটি ওইএম প্রতিটি পণ্যের জন্য m টি পার্ট কিনতে চায়। ওইএম পার্টস নিচের শর্তাবলী মেনে বেছে নেয়:
একই পার্টের দুটি বা তার অধিক ইউনিট কেনা যাবে না।
পার্টসের সেট এতভাবেই বেছে নেওয়া হবে যাতে মান V সর্বোচ্চ হয়, যেখানে V = |মোট রেটিং মাপদণ্ড A| + |মোট রেটিং মাপদণ্ড B| + |মোট রেটিং মাপদণ্ড C|।
আমাদের লক্ষ্য হলো ওইএম যে পার্টস বেছে নেবে সেখান থেকে V-র সর্বোচ্চ সম্ভাব্য মান বের করা।
যেমন, ইনপুট হলে n = 6, m = 4, ratings = {{2, 3, 5}, {3, 5, 2}, {4, 8, 5}, {1, 5, 3}, {7, 2, 7}, {4, 3, 6}}, তবে আউটপুট হবে 56।
যদি ওইএম পার্টস ১, ৩, ৫, এবং ৬ বেছে নেয়, তবে প্রতিটি ক্যাটাগরির মোট রেটিং হবে:
Category A = 2 + 4 + 7 + 4 = 17 Category B = 3 + 8 + 2 + 3 = 16. Category C = 5 + 5 + 7 + 6 = 23 V-র মোট মান = 17 + 16 + 23 = 56।
সমাধানের ধাপসমূহ
এই সমস্যাটি সমাধান করার জন্য নিচের ধাপগুলো অনুসরণ করব:
N := 100 arr অ্যারে সংজ্ঞায়িত করুন আকার: 9 x N। ans অ্যারে সংজ্ঞায়িত করুন। i := 0 থেকে n-1 পর্যন্ত: a := ratings[i]-র ১ম মান b := ratings[i]-র ২য় মান 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 i := 1 থেকে ৮ পর্যন্ত: arr[i] সোর্ট করুন i := 1 থেকে ৮ পর্যন্ত: arr[i] রিভার্স করুন if m == 0, তবে: V := 0 অন্যথায়: j := 1 থেকে ৮ পর্যন্ত: k := 0 i := 0 থেকে m-1 পর্যন্ত: k := k + arr[j, i] V := max(V, 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
