สุ่มเลือกด้วยน้ำหนักใน C++

สมมติว่าเรามีอาร์เรย์ w ของจำนวนเต็มบวก โดยที่ w[i] อธิบายน้ำหนักของดัชนี i เราต้องกำหนดฟังก์ชัน pickIndex() ซึ่งสุ่มเลือกดัชนีตามสัดส่วนของน้ำหนัก

ดังนั้นหากอินพุตเป็น [1,3] ให้เรียก pickIndex() ห้าครั้ง คำตอบอาจเป็น − 0, 1, 1, 1, 0

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

กำหนดอาร์เรย์ v
ผ่านตัวเริ่มต้น เริ่มต้นเป็น
n :=w[0]
สำหรับ i ในช่วง 1 ถึงขนาด w
- w[i] :=w[i] + w[i – 1]
- n :=w[i]
v =w
pickIndex() จะทำงานดังนี้ −
สุ่มตัวเลข r ดำเนินการ r mod องค์ประกอบสุดท้ายของ v
เอาจำนวนที่น้อยที่สุด ไม่น้อยกว่า r จาก v แล้วลบเลขแรกของ 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.

ผลลัพธ์