The Legacy Solver: The Knapsack Algorithm for Subset Sums

When the "Perfect Fit" (BnB) fails to find a solution, the wallet falls back to its "Workhorse": the Knapsack Solver. This algorithm is named after the classic mathematical "Knapsack Problem": if you have a bag of a certain size, and a collection of items of different values and weights, which items should you put in the bag to maximize the value? In Bitcoin, we use this to find a set of coins that is "At Least" the target amount, but as close as possible to it. The Knapsack Solver is a "Stochastic Approximation" algorithm, meaning it uses "Randomness" to find a good solution quickly. It is the "Resilience of the Core."

The Knapsack algorithm is the "Legacy Solver" of Bitcoin. It has been in the code since the early days and is designed to be "Guaranteed" to find a solution if you have enough money. Unlike BnB, it doesn't care about "Avoiding Change." It will happily create a change output if it means completing the payment. It is the "Reliability of the Bank," ensuring that the "Money Always Moves."

Analyzing the Random Solver: KnapsackSolver

In the source code (src/wallet/coinselection.cpp), we can see how the Knapsack logic works. It uses a series of "Passes" to find the best approximation of the target.

/**
 * This is the Knapsack Solver. It uses random "Guesses" to find the best subset of coins.
 */
util::Result<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, ...)
{
 // 1. We "Shuffle" the coins to ensure we don't pick the same ones every time.
 // This provides a tiny bit of "Privacy through Randomness."
 std::shuffle(groups.begin(), groups.end(), rng);

 // 2. The "Approximation Pass." We try 1,000 random combinations.
 // We look for the set that is closest to our target without going under.
 ApproximateBestSubset(rng, applicable_groups, nTotalLower, nTargetValue, vfBest, nBest, ...);

 // 3. If we found a "Good Enough" set...
 if (nBest >= nTargetValue) {
 // We add the selected coins to the final transaction draft.
 for (int i = 0; i < groups.size(); i++) {
 if (vfBest[i]) result.AddInput(groups[i]);
 }
 }

 return result;
}

Explaining the Knapsack: The Random Grab

• std::shuffle: If you always used the "Oldest" coins first, a spy could easily guess which coins are yours. By "Shuffling" the deck before every payment, Bitcoin Core ensures that your selection pattern is "Random." This makes it much harder for someone to "Fingerprint" your wallet's behavior. It is the "Security of the Random."

• ApproximateBestSubset: This is the "Guessing Game." The computer picks a random set of coins and checks the total. Then it picks another set. It does this 1,000 times in a fraction of a second. It keeps track of the "Best Guess" (the one closest to the target) and uses that for your transaction. This is a "Heuristic" approach—it's not mathematically "Perfect," but it's "Good Enough" for 99% of real-world payments. It is the "Practicality of the Forge."

• lowest_larger: The Knapsack solver has a "Safety Valve." If it has one single coin that is LARGER than the target, it will always consider using just that one coin. This is often the "Cleanest" fallback. Instead of spending 50 tiny coins, it just spends one big one and gets change back. This keeps your transaction "Small" and your fees low. It is the "Wisdom of the Single Piece."

The "Change-Heavy" Reality

The downside of the Knapsack solver is that it often creates "Change Outputs." Over time, your wallet will fill up with hundreds of tiny "Leftover" coins (Dust). This is why a Sovereign Architect must occasionally perform "Consolidation"—manually picking all those tiny coins and sending them to yourself in one single transaction. This "Pruning of the Vault" keeps your bank healthy and ensures your future transactions remain cheap. The Knapsack solver is your "Steady Worker," ensuring that the check always clears, even if the "Accounting" is a bit messy. You are the "Manager of the Health," the one who ensures the vault never fills with dust.