Branch and Bound explores include/exclude decisions for each item while computing an optimistic upper bound using fractional knapsack logic. Nodes whose bound is below current best are pruned.
struct Item { int w, v; double r; };
struct Node { int lvl, w, val; double bound; };
double ubound(Node u, int W, vector<Item>& a) {
if (u.w >= W) return 0;
double profit = u.val;
int j = u.lvl + 1, tw = u.w;
while (j < (int)a.size() && tw + a[j].w <= W) { tw += a[j].w; profit += a[j].v; j++; }
if (j < (int)a.size()) profit += (W - tw) * a[j].r;
return profit;
}Upper bound estimates the best possible value below a node.
If bound <= current best, subtree cannot improve answer and is discarded.
Sorting by value/weight improves pruning quality.
Quiz coming soon for this algorithm.