Chọn ngẫu nhiên theo trọng số (Random Pick with Weight) trong C++

Cho mảng trọng số w, hàm pickIndex() trả về chỉ số với xác suất tỷ lệ với trọng số.

Thuật toán (Prefix Sum + Binary Search)

1. Xây dựng mảng tiền tố prefix[i] = sum(w[0..i]).
2. Sinh ngẫu nhiên r trong [1, prefix.back()].
3. Dùng upper_bound tìm chỉ số đầu tiên ≥ r.

Mã nguồn C++

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

class Solution {
    vector prefix;
public:
    Solution(vector& w) {
        prefix = w;
        for (int i=1; i v = {1,3};
    Solution ob(v);
    for (int i=0; i<5; i++) cout << ob.pickIndex() << " ";
    return 0;
}

Đầu ra mẫu

1 1 1 1 0 (ngẫu nhiên)