แบ่งอาร์เรย์เพื่อให้ค่าเฉลี่ยเท่ากัน (Split Array With Same Average) ใน C++

ภาพรวมปัญหา

สมมติว่าเรามีอาร์เรย์ A เราต้องย้ายทุกสมาชิกของ A ไปอยู่ในลิสต์ B หรือลิสต์ C (ทั้งสองเริ่มว่าง) ตรวจสอบว่าหลังจากย้ายแล้ว ค่าเฉลี่ยของ B เท่ากับค่าเฉลี่ยของ C ได้หรือไม่ โดย B และ C ต้องไม่ว่าง

ตัวอย่าง

Input: [1,2,3,4,5,6,7,8,9,10] → Output: true (1)

แนวทางแก้ปัญหา (Dynamic Programming)

n := ขนาด A, total := ผลรวมทั้งหมด
ตรวจสอบว่ามี i (1 ถึง n/2) ที่ทำให้ total × i หาร n ลงตัวหรือไม่
ใช้ DP: dp[j][l] = true ถ้าสามารถเลือก l ตัวที่ผลรวมเป็น j ได้
dp[0][0] = true
อัปเดต DP แบบ 0/1 knapsack
ตรวจสอบว่ามี i ที่ (total × i) % n == 0 และ dp[total × i / n][i] == true

ตัวอย่างโปรแกรม

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

class Solution {
public:
    bool splitArraySameAverage(vector<int>& A) {
        int n = A.size();
        int total = 0;
        for(int i = 0; i < n; i++) total += A[i];
        
        bool isPossible = false;
        int m = n / 2;
        for (int i = 1; i <= m && !isPossible; ++i)
            if (total * i % n == 0) isPossible = true;
        if (!isPossible) return false;
        
        vector<vector<bool>> dp(total + 1, vector<bool>((n / 2) + 1));
        dp[0][0] = true;
        
        for(int i = 0; i < n; i++) {
            int x = A[i];
            for(int j = total; j >= x; j--) {
                for(int l = 1; l <= (n / 2); l++) {
                    dp[j][l] = dp[j][l] || dp[j - x][l - 1];
                }
            }
        }
        
        for(int i = 1; i <= (n / 2); i++) {
            if((total * i) % n == 0 && dp[total * i / n][i]) return true;
        }
        return false;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,2,3,4,5,6,7,8,9,10};
    cout << (ob.splitArraySameAverage(v));
}

Input

{1,2,3,4,5,6,7,8,9,10}