Tối đa hóa xác suất chọn loại X từ N container trong C++

Xác suất P = (Số kết quả thuận lợi) / (Tổng số kết quả).

Cho N container và N bản sao của hai loại X và Y. Nhiệm vụ: phân phối N bản sao của X vào N container sao cho xác suất rút được X là lớn nhất.

Để tối đa P, ta có thể: tối đa hóa tử số (số X) hoặc tối thiểu hóa mẫu số (tổng số phần tử). Chiến lược tối ưu:

• N-1 container chứa 1 bản sao X mỗi container.
• 1 container chứa 1 bản sao Y và N bản sao X (còn lại).

Xác suất rút X từ N-1 container đầu: P_n-1 = 1

Xác suất rút X từ container cuối: P_n = 1/(N+1)

Xác suất tổng thể: P_m = P_n-1 × (N-1)/N + P_n × 1/N = (N-1)/N + 1/(N(N+1)) = N/(N+1)

Ví dụ

Input – N = 1

Output – Xác suất max = 0.5

Giải thích: 1 container, 1 X và 1 Y → P = 1/2 = 0.5

Input – N = 3

Output – Xác suất max = 0.75

Giải thích: 2 container có 1 X, 1 container có 1 Y + 3 X. P = 3/4 = 0.75

Thuật toán

1. Nhập N (số container).
2. Tính maxP = N / (N + 1).
3. In kết quả.

Ví dụ code

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

int main() {
    int N = 3;
    double maxP = (double)N / (N + 1);
    cout << "Maximum Probability for N = " << N << " is: " << maxP << endl;
    return 0;
}

Kết quả

Maximum Probability for N = 3 is: 0.75

Chứng minh tối ưu: Đây là bài toán kinh điển "Two Urns Problem" hoặc "Maximizing Probability". Chiến lược trên được chứng minh là tối ưu bằng bất đẳng thức Cauchy-Schwarz hoặc phân tích đạo hàm.