#### Branch and bound solver

```using System;
using System.Collections.Generic;
using System.Linq;

namespace Algorithms.Knapsack
{
/// <summary>
///     Branch and bound Knapsack solver.
/// </summary>
/// <typeparam name="T">Type of items in knapsack.</typeparam>
public class BranchAndBoundKnapsackSolver<T>
{
/// <summary>
///     Returns the knapsack containing the items that maximize value while not exceeding weight capacity.
///     Construct a tree structure with total number of items + 1 levels, each node have two child nodes,
///     starting with a dummy item root, each following levels are associated with 1 items, construct the
///     tree in breadth first order to identify the optimal item set.
/// </summary>
/// <param name="items">All items to choose from.</param>
/// <param name="capacity">The maximum weight capacity of the knapsack to be filled.</param>
/// <param name="weightSelector">
///     A function that returns the value of the specified item
///     from the <paramref name="items">items</paramref> list.
/// </param>
/// <param name="valueSelector">
///     A function that returns the weight of the specified item
///     from the <paramref name="items">items</paramref> list.
/// </param>
/// <returns>
///     The array of items that provides the maximum value of the
///     knapsack without exceeding the specified weight <paramref name="capacity">capacity</paramref>.
/// </returns>
public T[] Solve(T[] items, int capacity, Func<T, int> weightSelector, Func<T, double> valueSelector)
{
// This is required for greedy approach in upper bound calculation to work.
items = items.OrderBy(i => valueSelector(i) / weightSelector(i)).ToArray();

// nodesQueue --> used to construct tree in breadth first order
Queue<BranchAndBoundNode> nodesQueue = new();

// maxCumulativeValue --> maximum value while not exceeding weight capacity.
var maxCumulativeValue = 0.0;

// starting node, associated with a temporary created dummy item
BranchAndBoundNode root = new(level: -1, taken: false);

// lastNodeOfOptimalPat --> last item in the optimal item sets identified by this algorithm
BranchAndBoundNode lastNodeOfOptimalPath = root;

nodesQueue.Enqueue(root);

while (nodesQueue.Count != 0)
{
// parent --> parent node which represents the previous item, may or may not be taken into the knapsack
BranchAndBoundNode parent = nodesQueue.Dequeue();

// IF it is the last level, branching cannot be performed
if (parent.Level == items.Length - 1)
{
continue;
}

// create a child node where the associated item is taken into the knapsack
var left = new BranchAndBoundNode(parent.Level + 1, true, parent);

// create a child node where the associated item is not taken into the knapsack
var right = new BranchAndBoundNode(parent.Level + 1, false, parent);

// Since the associated item on current level is taken for the first node,
// set the cumulative weight of first node to cumulative weight of parent node + weight of the associated item,
// set the cumulative value of first node to cumulative value of parent node + value of current level's item.
left.CumulativeWeight = parent.CumulativeWeight + weightSelector(items[left.Level]);
left.CumulativeValue = parent.CumulativeValue + valueSelector(items[left.Level]);
right.CumulativeWeight = parent.CumulativeWeight;
right.CumulativeValue = parent.CumulativeValue;

// IF cumulative weight is smaller than the weight capacity of the knapsack AND
// current cumulative value is larger then the current maxCumulativeValue, update the maxCumulativeValue
if (left.CumulativeWeight <= capacity && left.CumulativeValue > maxCumulativeValue)
{
maxCumulativeValue = left.CumulativeValue;
lastNodeOfOptimalPath = left;
}

left.UpperBound = ComputeUpperBound(left, items, capacity, weightSelector, valueSelector);
right.UpperBound = ComputeUpperBound(right, items, capacity, weightSelector, valueSelector);

// IF upperBound of this node is larger than maxCumulativeValue,
// the current path is still possible to reach or surpass the maximum value,
// add current node to nodesQueue so that nodes below it can be further explored
if (left.UpperBound > maxCumulativeValue && left.CumulativeWeight < capacity)
{
nodesQueue.Enqueue(left);
}

// Cumulative weight is the same as for parent node and < capacity
if (right.UpperBound > maxCumulativeValue)
{
nodesQueue.Enqueue(right);
}
}

return GetItemsFromPath(items, lastNodeOfOptimalPath);
}

// determine items taken based on the path
private static T[] GetItemsFromPath(T[] items, BranchAndBoundNode lastNodeOfPath)
{
List<T> takenItems = new();

// only bogus initial node has no parent
for (var current = lastNodeOfPath; current.Parent is not null; current = current.Parent)
{
if(current.IsTaken)
{
}
}

return takenItems.ToArray();
}

/// <summary>
///     Returns the upper bound value of a given node.
/// </summary>
/// <param name="aNode">The given node.</param>
/// <param name="items">All items to choose from.</param>
/// <param name="capacity">The maximum weight capacity of the knapsack to be filled.</param>
/// <param name="weightSelector">
///     A function that returns the value of the specified item
///     from the <paramref name="items">items</paramref> list.
/// </param>
/// <param name="valueSelector">
///     A function that returns the weight of the specified item
///     from the <paramref name="items">items</paramref> list.
/// </param>
/// <returns>
///     upper bound value of the given <paramref name="aNode">node</paramref>.
/// </returns>
private static double ComputeUpperBound(BranchAndBoundNode aNode, T[] items, int capacity, Func<T, int> weightSelector, Func<T, double> valueSelector)
{
var upperBound = aNode.CumulativeValue;
var availableWeight = capacity - aNode.CumulativeWeight;
var nextLevel = aNode.Level + 1;

while (availableWeight > 0 && nextLevel < items.Length)
{
if (weightSelector(items[nextLevel]) <= availableWeight)
{
upperBound += valueSelector(items[nextLevel]);
availableWeight -= weightSelector(items[nextLevel]);
}
else
{
upperBound += valueSelector(items[nextLevel]) / weightSelector(items[nextLevel]) * availableWeight;
availableWeight = 0;
}

nextLevel++;
}

return upperBound;
}
}
}
```  