Chọn ngẫu nhiên với Trọng lượng trong C ++

Giả sử chúng ta có một mảng w gồm các số nguyên dương, được w [i] mô tả trọng số của chỉ số i, chúng ta phải xác định một hàm pickIndex () chọn ngẫu nhiên một chỉ mục tương ứng với trọng số của nó.

Vì vậy, nếu đầu vào là [1,3], hãy gọi pickIndex () năm lần, thì câu trả lời có thể là - 0, 1, 1, 1, 0.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một mảng v,
• Thông qua trình khởi tạo, hãy khởi tạo dưới dạng
• n:=w [0]
• cho tôi trong phạm vi từ 1 đến kích thước của w
  • w [i]:=w [i] + w [i - 1]
  • n:=w [i]
• v =w
• PickIndex () sẽ hoạt động như sau -
• Lấy một số ngẫu nhiên r, thực hiện r mod phần tử cuối cùng của v
• lấy số nhỏ nhất, không nhỏ hơn r từ v, sau đó trừ số đầu tiên của v khỏi phần tử và trả về.

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int n;
   vector <int> v;
   Solution(vector<int>& w) {
      srand(time(NULL));
      n = w[0];
      for(int i = 1; i < w.size(); i++){
         w[i] += w[i - 1];
         n = w[i];
      }
      v = w;
   }
   int pickIndex() {
      return upper_bound(v.begin(), v.end(), rand() % v.back()) - v.begin();
   }
};
main(){
   vector<int> v = {1,3};
   Solution ob(v);
   cout << (ob.pickIndex()) << endl;
   cout << (ob.pickIndex()) << endl;
   cout << (ob.pickIndex()) << endl;
   cout << (ob.pickIndex()) << endl;
   cout << (ob.pickIndex()) << endl;
}

Đầu vào

Initialize with [1, 3] and call pickIndex five times.

Đầu ra

1
1
1
1
0