342{
343 int choices = 1, others = 0;
344
345 if (k > n / 2)
346 {
347 choices = 0;
348 others = 1;
349 k = n - k;
350 }
351
352
353 float * cumulative = new float [n + 1];
354
355 cumulative[0] = 0;
356 for (int i = 1; i <= n; i++)
357 cumulative[i] = cumulative[i - 1] + weights[i - 1];
358
359 float & sum = cumulative[n], reject = 0.0;
360
361 for (int i = 0; i < n; i++)
362 array[i] = others;
363
364 while (k > 0)
365 {
366 float weight = Next() * sum;
367
368 int hi = n, lo = 0, i = 0;
369
370 while (hi >= lo)
371 {
372 i = (hi + lo) / 2;
373
374 if (cumulative[i + 1] <= weight)
375 lo = i + 1;
376 else if (cumulative[i] >= weight)
377 hi = i - 1;
378 else break;
379 }
380
381 if (array[i] == choices) continue;
382
383 array[i] = choices;
384 reject += weights[i];
385
386
387
388 if (reject > sum * 0.50)
389 {
390 cumulative[0] = 0;
391 for (int i = 1; i <= n; i++)
392 if (array[i] != choices)
393 cumulative[i] = cumulative[i - 1] + weights[i - 1];
394 else
395 cumulative[i] = cumulative[i - 1];
396
397 reject = 0.0;
398 sum = cumulative[n];
399 }
400
401 k--;
402 }
403
404 delete [] cumulative;
405}