B&B, a quick one

ks.cpp

struct Item {
    Item() = default;
    Item(int value, int weight) : value_(value), weight_(weight) {
    }

    int value_;
    int weight_;
};

struct Node {
    Node() = default;
    Node(int accum_val, int accum_weight, int level)
        : accum_val_(accum_val), accum_weight_(accum_weight), level_(level) {
    }

    int accum_val_;
    int accum_weight_;
    int level_;
    int estimation_;
};

bool ByDensity(const Item* lhs, const Item* rhs) {
    double lden = static_cast<double>(lhs->value_) / lhs->weight_;
    double rden = static_cast<double>(rhs->value_) / rhs->weight_;
    return lden > rden;
}

void DensitySort(std::vector<const Item*>& items) {
    std::sort(items.begin(), items.end(), ByDensity);
}

size_t Greedy(const Node& node, int capacity, const std::vector<const Item*>& pointers) {
    if (node.accum_weight_ >= capacity) {
        return 0;
    }
    int curcap = node.accum_weight_;
    size_t ind = node.level_ + 1;
    int cost = node.accum_val_;
    for (; ind < pointers.size(); ++ind) {
        auto [value, weight] = *(pointers.at(ind));
        if (curcap + weight <= capacity) {
            curcap += weight;
            cost += value;
        } else {
            break;
        }
    }
    if (ind < pointers.size()) {
        auto [value, weight] = *(pointers.at(ind));
        cost += (static_cast<double>(capacity - curcap) / weight) * value;
    }
    return cost;
}

size_t BranchAndBound(int capacity, const std::vector<Item>& items) {
    std::vector<int> indexes;
    std::vector<const Item*> pointers;
    pointers.reserve(items.size());
    for (size_t ind = 0; ind < items.size(); ++ind) {
        pointers.push_back(&(items.at(ind)));
    }
    DensitySort(pointers);
    std::queue<Node> que;
    Node root(0, 0, -1);
    Node next;
    que.push(root);
    int cost = 0;
    while (!que.empty()) {
        next = que.front();
        que.pop();
        if (next.level_ == -1) {
            root.level_ = 0;
        }
        if (next.level_ + 1 != static_cast<int>(items.size())) {
            root.level_ = next.level_ + 1;
            root.accum_weight_ = next.accum_weight_ + pointers.at(root.level_)->weight_;
            root.accum_val_ = next.accum_val_ + pointers.at(root.level_)->value_;
            if (root.accum_weight_ <= capacity && root.accum_val_ > cost) {
                cost = root.accum_val_;
            }
            root.estimation_ = Greedy(root, capacity, pointers);
            if (root.estimation_ > cost) {
                que.push(root);
            }
            root.accum_weight_ = next.accum_weight_;
            root.accum_val_ = next.accum_val_;
            root.estimation_ = Greedy(root, capacity, pointers);
            if (root.estimation_ > cost) {
                que.push(root);
            }
        }
    }
    return cost;
}