CP-ANSWER-UNDER-LIMITS - Obtain the answer the work needs within available resources

• Situation: A finite selection problem is expensive; changing from one best selection to every best selection can invalidate a shortcut.
• Question: How can construction, sharing, bounds and retained information preserve the answer now required?
• First useful result or blocker: An answer-producing procedure with justified exclusions and sufficient reconstruction information, or the specific resource limit it cannot meet.
• Start with: CMP.2, then CMP.3 when subproblems repeat. A useful bound from CMP.5 can justify exclusions in CMP.4.
• Stop or return: Stop at the answer sufficient for the work. Changed data, completeness or permitted error reopen the choices that depended on them; a faster value computation need not retain every witness.

First specify whether the result is a value, one selection attaining it, all such selections, or an allowed approximation. CMP.2 - Derive a Recursive Procedure from a Problem Decomposition constructs subproblems with enough returned information to assemble that answer. CMP.3 - Share and Schedule Repeated Subcomputations uses their identity and dependencies to decide what can be computed once, when it is needed, and what must remain available for reconstruction.

CMP.Preface:4 supplies a small connected case. Each distinct item may be selected at most once; costs and values add, and capacity is 5.

Let R(i,b) be the best value using the first i items within capacity b. CMP.2 separates exclusion of the next item from its feasible inclusion. CMP.3 shares each resulting (i,b) subproblem. The final values for capacities 0 through 5 are 0, 0, 3, 5, 7, 8; B+C attains 8. Keeping only two rows can save value-storage, but recovering a selection still needs choices or justified recomputation. CMP.10 chooses a representation for those actual accesses and retained distinctions. The table uses order nW updates for n items and integer capacity W; that is not a polynomial bound in the number of bits encoding W.

If exploring alternatives remains expensive, CMP.5 - Bound an Optimum or Recover a Feasible Candidate through a Relaxed Problem permits fractional items to obtain an upper bound. A plus one third of B gives the fractional optimum 26/3. Since original values are integers, they cannot exceed 8. B+C reaches 8, so the optimum is already settled. CMP.4 - Construct Computational Search with Justified Exclusions consumes such a bound to exclude alternatives; it does not treat an arbitrary relaxed candidate as an upper bound.

Now add D with cost 4 and value 8, and request every optimal selection. Both D and B+C must survive. The old bound concerned a different item set: D plus one quarter of A gives the new fractional optimum 39/4, so its integer upper bound is 9 and does not alone settle optimality. The updated recurrence gives optimum 8. At its final state both the exclude-D and include-D branches attain 8; following both recovers the two selections.

The output change also changes pruning: for one optimum, an upper bound U <= L, where L is an attained value, excludes a branch that cannot improve it. For all optima, equality can hide another required selection, so this exclusion needs U < L. Storing only the cheapest selection for each value would keep D and discard B+C; following ties later cannot restore information already lost. Return to the recurrence and retain the required choices and item identities. Listing all answers can itself require much more work than computing their common value.

If a near-optimal answer would actually suffice, CMP.8 - Construct an Approximate Computation with Controlled Error changes the permitted error and construction; it does not answer the request for all exact optima. If the disputed question is what any algorithm must spend, CMP.11 - Derive a Computational Lower Bound from Indistinguishable Inputs requires a stated access and cost model. One slow implementation establishes no such limit. Other selection problems need their own sufficient subproblems and valid bounds; the item table is an example of the joins, not their scope.