特定の製品の特定の部品を製造するメーカーがあるとします。メーカーは、3 つの規格に基づいて特定の定格を持つ部品のさまざまなバリエーションを用意しています。 n 製品の評価は配列 '評価' で与えられます。各要素は (A、B、C) の形式で、A、B、C は製品の異なる評価基準です。ここで、OEM は各製品に必要な m 個の部品を部品メーカーから購入したいと考えています。 OEM は、次の条件を満たす部品を選択します:
同じ部品を 2 つ以上購入することはできません。
値 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
以上が定格部品の最大セットを見つけるための C++ プログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。