Implementation of Branch-and-Bound coin selection defined in Erhart's
    Master's thesis An Evaluation of Coin Selection Strategies here:
    http://murch.one/wp-content/uploads/2016/11/erhardt2016coinselection.pdf

    :param target: The total amount of the outputs in a transaction for which
                   we try to select the inputs to spend.
    :type target: ``int``
    :param fee: The number of satoshi per byte for the fee of the transaction.
    :type fee: ``int``
    :param output_size: A list containing as int the sizes of each output.
    :type output_size: ``list`` of ``int`
    :param min_change: The minimum amount of satoshis allowed for the
                       return/change address if there is no perfect match.
    :type min_change: ``int``
    :param absolute_fee: Whether or not the parameter ``fee`` should be
                         repurposed to denote the exact fee amount.
    :type absolute_fee: ``bool``
    :param consolidate: Whether or not the Branch-and-Bound process for finding
                        a perfect match should be skipped and all unspents
                        used directly.
    :type consolidate: ``bool``
    :param unspents: The UTXOs to use as inputs.
    :type unspents: ``list`` of :class:`~bit.network.meta.Unspent`
    :raises InsufficientFunds: If ``unspents`` does not contain enough balance
                               to allow spending matching the target.

def select_coins(target, fee, output_size, min_change, *, absolute_fee=False,
                 consolidate=False, unspents):
    '''
    Implementation of Branch-and-Bound coin selection defined in Erhart's
    Master's thesis An Evaluation of Coin Selection Strategies here:
    http://murch.one/wp-content/uploads/2016/11/erhardt2016coinselection.pdf

    :param target: The total amount of the outputs in a transaction for which
                   we try to select the inputs to spend.
    :type target: ``int``
    :param fee: The number of satoshi per byte for the fee of the transaction.
    :type fee: ``int``
    :param output_size: A list containing as int the sizes of each output.
    :type output_size: ``list`` of ``int`
    :param min_change: The minimum amount of satoshis allowed for the
                       return/change address if there is no perfect match.
    :type min_change: ``int``
    :param absolute_fee: Whether or not the parameter ``fee`` should be
                         repurposed to denote the exact fee amount.
    :type absolute_fee: ``bool``
    :param consolidate: Whether or not the Branch-and-Bound process for finding
                        a perfect match should be skipped and all unspents
                        used directly.
    :type consolidate: ``bool``
    :param unspents: The UTXOs to use as inputs.
    :type unspents: ``list`` of :class:`~bit.network.meta.Unspent`
    :raises InsufficientFunds: If ``unspents`` does not contain enough balance
                               to allow spending matching the target.
    '''

    # The maximum number of tries for Branch-and-Bound:
    BNB_TRIES = 1000000

    # COST_OF_OVERHEAD excludes the return address of output_size (last element).
    COST_OF_OVERHEAD = (8 + sum(output_size[:-1]) + 1) * fee

    def branch_and_bound(d, selected_coins, effective_value, target, fee,
                         sorted_unspents):  # pragma: no cover

        nonlocal COST_OF_OVERHEAD, BNB_TRIES
        BNB_TRIES -= 1
        COST_PER_INPUT = 148 * fee  # Just typical estimate values
        COST_PER_OUTPUT = 34 * fee

        # The target we want to match includes cost of overhead for transaction
        target_to_match = target + COST_OF_OVERHEAD
        # Allowing to pay fee for a whole input and output is rationally
        # correct, but increases the fee-rate dramatically for only few inputs.
        match_range = COST_PER_INPUT + COST_PER_OUTPUT
        # We could allow to spend up to X% more on the fees if we can find a
        # perfect match:
        # match_range += int(0.1 * fee * sum(u.vsize for u in selected_coins))

        # Check for solution and cut criteria:
        if effective_value > target_to_match + match_range:
            return []
        elif effective_value >= target_to_match:
            return selected_coins
        elif BNB_TRIES <= 0:
            return []
        elif d >= len(sorted_unspents):
            return []
        else:
            # Randomly explore next branch:
            binary_random = randint(0, 1)
            if binary_random:
                # Explore inclusion branch first, else omission branch:
                effective_value_new = effective_value + \
                    sorted_unspents[d].amount - fee * sorted_unspents[d].vsize

                with_this = branch_and_bound(
                    d + 1,
                    selected_coins + [sorted_unspents[d]],
                    effective_value_new,
                    target,
                    fee,
                    sorted_unspents
                )

                if with_this != []:
                    return with_this
                else:
                    without_this = branch_and_bound(
                        d + 1,
                        selected_coins,
                        effective_value,
                        target,
                        fee,
                        sorted_unspents
                    )

                    return without_this

            else:
                # As above but explore omission branch first:
                without_this = branch_and_bound(
                    d + 1,
                    selected_coins,
                    effective_value,
                    target,
                    fee,
                    sorted_unspents
                )

                if without_this != []:
                    return without_this
                else:
                    effective_value_new = effective_value + \
                        sorted_unspents[d].amount - fee * sorted_unspents[d].vsize

                    with_this = branch_and_bound(
                        d + 1,
                        selected_coins + [sorted_unspents[d]],
                        effective_value_new,
                        target,
                        fee,
                        sorted_unspents
                    )

                    return with_this

    sorted_unspents = sorted(unspents, key=lambda u: u.amount, reverse=True)
    selected_coins = []

    if not consolidate:
        # Trying to find a perfect match using Branch-and-Bound:
        selected_coins = branch_and_bound(
            d=0,
            selected_coins=[],
            effective_value=0,
            target=target,
            fee=fee,
            sorted_unspents=sorted_unspents
        )
        remaining = 0

    # Fallback: If no match, Single Random Draw with return address:
    if selected_coins == []:
        unspents = unspents.copy()
        # Since we have no information on the user's spending habit it is
        # best practice to randomly select UTXOs until we have enough.
        if not consolidate:
            # To have a deterministic way of inserting inputs when
            # consolidating, we only shuffle the unspents otherwise.
            shuffle(unspents)
        while unspents:
            selected_coins.append(unspents.pop(0))
            estimated_fee = estimate_tx_fee(
                sum(u.vsize for u in selected_coins),
                len(selected_coins),
                sum(output_size),
                len(output_size),
                fee
            )
            estimated_fee = fee if absolute_fee else estimated_fee
            remaining = sum(u.amount for u in selected_coins) - target - estimated_fee
            if remaining >= min_change and (not consolidate or len(unspents) == 0):
                break
        else:
            raise InsufficientFunds('Balance {} is less than {} (including '
                                    'fee).'.format(sum(
                                        u.amount for u in selected_coins),
                                        target + min_change + estimated_fee))

    return selected_coins, remaining