C++에서 가중치가 있는 무작위 선택

<시간/>

양의 정수 배열 w가 있다고 가정하고 w[i]가 인덱스 i의 가중치를 설명한다면 가중치에 비례하여 인덱스를 무작위로 선택하는 함수 pickIndex()를 정의해야 합니다.

따라서 입력이 [1,3]과 같으면 pickIndex()를 5번 호출하면 응답이 -0, 1, 1, 1, 0이 될 수 있습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

배열 v 정의,
이니셜라이저를 통해 다음과 같이 초기화합니다.
n :=w[0]
범위 1에서 w
- w[i] :=w[i] + w[i – 1]
- n :=w[i]
v =w
pickIndex()는 다음과 같이 작동합니다 -
난수 r을 선택하고 v의 마지막 요소를 r 모드로 수행
v에서 r보다 작지 않은 가장 작은 수를 취한 다음 요소에서 v의 첫 번째 수를 빼고 반환합니다.

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#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;
}

입력

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

출력