โปรแกรม C++ หาชุดชิ้นส่วนที่มีคะแนนรวมสูงสุด

ผู้ผลิตมีชิ้นส่วน n รุ่น แต่ละรุ่นมีคะแนน 3 เกณฑ์ (A,B,C) OEM ต้องการซื้อ m รุ่น (ไม่ซ้ำ) เพื่อเพิ่มค่า V = |ΣA| + |ΣB| + |ΣC| ให้สูงสุด

ตัวอย่าง: n=6,m=4, ratings={{2,3,5},{3,5,2},{4,8,5},{1,5,3},{7,2,7},{4,3,6}} ผลลัพธ์: 56 (เลือกชิ้นส่วน 1,3,5,6 → A=17, B=16, C=23)

ขั้นตอนการแก้ปัญหา (Enumerate Sign Patterns)

1. ค่า V = |ΣA|+|ΣB|+|ΣC| เทียบเท่ากับ max ของ ±ΣA ± ΣB ± ΣC 8 รูปแบบเครื่องหมาย
2. สำหรับแต่ละรูปแบบ 8 แบบ คำนวณค่า score_i ของแต่ละชิ้นส่วน:
   • 1: +A+B+C, 2: +A-B-C, 3: +A+B-C, 4: +A-B+C
   • 5: -A+B+C, 6: -A-B-C, 7: -A+B-C, 8: -A-B+C
3. เรียงแต่ละรูปแบบมาก→น้อย เลือก m อันดับแรก รวมคะแนน หาค่าสูงสุด

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

#define N 100
int solve(int n, int m, vector<tuple<int,int,int>> ratings) {
    int V, arr[9][N];
    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