Chương trình C++ tìm tập hợp bộ phận có tổng rating tuyệt đối lớn nhất

Mô tả bài toán

Có n biến thể bộ phận, mỗi loại có 3 tiêu chí rating (A,B,C). Chọn m loại khác nhau tối đa hóa V = |sum A| + |sum B| + |sum C|.

Ví dụ

n=6,m=4, ratings={{2,3,5},{3,5,2},{4,8,5},{1,5,3},{7,2,7},{4,3,6}}. Đầu ra: 56 (chọn 1,3,5,6).

Thuật toán (Tham lam 8 hướng)

1. Mỗi bộ phận tạo 8 giá trị: ±A ± B ± C (tất cả tổ hợp dấu).
2. Với mỗi trong 8 hướng, sắp xếp giảm dần, lấy m giá trị lớn nhất, tính tổng.
3. Kết quả = max 8 tổng này.
4. Đúng vì |sum A|+|sum B|+|sum C| = max_{dấu} sum(±A ± B ± C).

Đoạn mã C++

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

int solve(int n,int m,vector<tuple<int,int,int>> ratings){
    const int N=100;
    int arr[9][N];
    for(int i=0;i());
    int V=0;
    for(int j=1;j<=8;j++){
        int k=0;
        for(int i=0;i