The penalized DP gives optimal cost. But we also need to know how many elements were used. Modify DP to track pairs: . When adding an element, increment count. Comparison: first by cost, then by count (prefer fewer elements if costs are equal, or vice versa depending on problem). After DP, check if count equals .
If not, adjust and repeat. The count tells you whether to increase or decrease the penalty. Binary search converges to the right penalty.