[CSES] Apple Division

Đề bài

Có N quả táo, biết cân nặng của từng quả. Nhiệm vụ của bạn là chia táo thành hai nhóm sao cho tổng của chúng chênh lệch nhau nhỏ nhất.

Dữ liệu:

• Dòng đầu tiên chứa số nguyên N là số lượng quả táo ($1 \leq N \leq 20$).
• Dòng thứ hai chứa N số nguyên $a_1, a_2, a_3,…, a_N$ thể hiện khối lượng của từng quả táo ($1\leq a_i \leq 10^9$).

Kết quả:

• In ra độ chênh lệch nhỏ nhất có thể tìm được.

Ví dụ:

Giải thích

• [3,2,4] và [7,1] đây là cách chia để có độ chênh lệch là nhỏ nhất

Hướng dẫn

• Cách 1: Sử dụng phương pháp đệ quy – quay lui với phân tích: quả táo thứ i có thể thuộc vào nhóm 1 hoặc nhóm 2 ==> lấy min của 2 cách chọn. Cơ sở đệ quy: Khi xét đủ N quả táo thì lấy hiệu của tổng trọng lượng từ hai nhóm.

#include <bits/stdc++.h>
#define ll long long int
using namespace std;
 
ll Try(int idx, ll* arr, ll sum1, ll sum2, ll N)
{
    // If we have reached the end, return the difference
    // between the sums
    if (idx == N) {
        return abs(sum1 - sum2);
    }
 
    // Choose the current apple in group 1
    ll choose
        = Try(idx + 1, arr, sum1 + arr[idx], sum2, N);
 
    // Choose the current apple in group 2
    ll notChoose
        = Try(idx + 1, arr, sum1, sum2 + arr[idx], N);
 
    // Return the minimum of both the choices
    return min(choose, notChoose);
}
 
int main()
{
    // Sample Input
    ll N ; cin>>N;
    ll arr[N];
    for(int i=0;i<N;i++) cin>>arr[i];
 
    // Call the recursive function to find the minimum
    // difference between both the groups
    ll ans = Try(0, arr, 0, 0, N);
    cout << ans;
}

• Cách 2: Dùng kỹ thuật xét các xâu nhị phân để thể hiện sự chọn hoặc không chọn. Ta sẽ duyệt qua tất cả các xâu nhị phân độ dài N (theo thứ tự). Khi đó ta sẽ xem xét rằng bit ở vị trí thứ i bằng 0 hay 1. Nếu bằng 0 thì ta sẽ chọn nó vào group1, ngược lại sẽ chọn vào group2. Rồi chúng ta sẽ update lại kết quả sau những lần duyệt xâu nhị phân.

Mã nguồn tham khảo

#include <bits/stdc++.h>
using namespace std;
#define task "test"
const int N = 21;
int n;
int a[N];
int get_bit(int mask ,int i){
    return (mask>>i)&1;
}
void run(){
    cin >> n;
    for(int i=0;i<n;i++) cin >> a[i];
    long long ans= 1e9;
    for(int mask=1 ; mask<(1<<n) ; mask++){
        long long  sum_a=0, sum_b=0;
        for(int i=0;i<n;i++){
            if(get_bit(mask, i)) sum_a+=a[i];
            else sum_b+=a[i];
        }
        ans = min(ans, abs(sum_a-sum_b));
    }
    cout << ans; 
}
int main()
{
    run();
}