| 584 | |
| 585 | namespace { |
| 586 | void |
| 587 | knapsack (const std::vector<Long>& wgts, |
| 588 | int nprocs, |
| 589 | std::vector< std::vector<int> >& result, |
| 590 | Real& efficiency, |
| 591 | bool do_full_knapsack, |
| 592 | int nmax) |
| 593 | { |
| 594 | BL_PROFILE("knapsack()"); |
| 595 | |
| 596 | // |
| 597 | // Sort balls by size largest first. |
| 598 | // |
| 599 | result.resize(nprocs); |
| 600 | |
| 601 | Vector<WeightedBox> lb; |
| 602 | lb.reserve(wgts.size()); |
| 603 | for (int i = 0, N = static_cast<int>(wgts.size()); i < N; ++i) |
| 604 | { |
| 605 | lb.emplace_back(i, wgts[i]); |
| 606 | } |
| 607 | std::sort(lb.begin(), lb.end()); |
| 608 | // |
| 609 | // For each ball, starting with heaviest, assign ball to the lightest bin. |
| 610 | // |
| 611 | std::priority_queue<WeightedBoxList> wblq; |
| 612 | Vector<std::unique_ptr<Vector<WeightedBox> > > raii_vwb(nprocs); |
| 613 | for (int i = 0; i < nprocs; ++i) |
| 614 | { |
| 615 | raii_vwb[i] = std::make_unique<Vector<WeightedBox> >(); |
| 616 | wblq.push(WeightedBoxList{.m_lb = raii_vwb[i].get(), |
| 617 | .m_weight = Long(0), |
| 618 | .m_rank = -1}); |
| 619 | } |
| 620 | Vector<WeightedBoxList> wblv; |
| 621 | wblv.reserve(nprocs); |
| 622 | for (unsigned int i = 0, N = wgts.size(); i < N; ++i) |
| 623 | { |
| 624 | if (!wblq.empty()) { |
| 625 | WeightedBoxList wbl = wblq.top(); |
| 626 | wblq.pop(); |
| 627 | wbl.push_back(lb[i]); |
| 628 | if (wbl.size() < nmax) { |
| 629 | wblq.push(wbl); |
| 630 | } else { |
| 631 | wblv.push_back(wbl); |
| 632 | } |
| 633 | } else { |
| 634 | int ip = static_cast<int>(i) % nprocs; |
| 635 | wblv[ip].push_back(lb[i]); |
| 636 | } |
| 637 | } |
| 638 | |
| 639 | Real max_weight = 0; |
| 640 | Real sum_weight = 0; |
| 641 | for (auto const& wbl : wblv) |
| 642 | { |
| 643 | Real wgt = static_cast<Real>(wbl.weight()); |