按比例分配多面额现金的算法实现需求及求解问询

首先，你的思路方向没问题，但递归其实不是最优选择——毕竟咱们的面额是固定的四种，还有明确的占比要求，用贪心计算基础张数+微调的方式会更直接高效。下面我一步步拆解解法，再给你Java代码示例。

核心思路 #

我们的目标是让各面额金额占比尽可能贴近要求（$100占30%、$20占40%、$5占20%、$1占10%），同时总金额尽可能接近给定目标。具体步骤如下：

• 第一步：计算理论目标金额：用总目标金额乘以对应占比，得到每个面额的理想金额。
• 第二步：转换为整数张数：把理论金额除以面额取整（用四舍五入更贴近理论值），得到基础张数。
• 第三步：微调总金额：计算当前基础张数的总金额和目标的差值，优先用最小面额（$1）调整——因为小面额的调整对整体占比影响最小，能最大程度保留大面额的占比精度。如果差值过大，再依次往上调整更大面额。

关键注意点 #

• 纸币张数必须是整数，所以占比不可能完全精确，我们要做的是尽可能接近要求占比的同时，让总金额最贴近目标。
• 优先保证大面额的占比精度，因为大面额的金额波动对总占比的影响远大于小面额。

Java代码示例 #

import java.math.BigDecimal;
import java.math.RoundingMode;

public class CashAllocator {
    // 定义面额（从大到小排序）和对应占比
    private static final int[] DENOMINATIONS = {100, 20, 5, 1};
    private static final double[] TARGET_RATIOS = {0.3, 0.4, 0.2, 0.1};

    public static void allocateCash(int targetAmount) {
        int[] counts = new int[DENOMINATIONS.length];
        int currentTotal = 0;

        // 第一步：计算各面额的基础张数
        for (int i = 0; i < DENOMINATIONS.length; i++) {
            double theoreticalAmount = targetAmount * TARGET_RATIOS[i];
            // 四舍五入得到理论张数
            int theoreticalCount = (int) Math.round(theoreticalAmount / DENOMINATIONS[i]);
            counts[i] = theoreticalCount;
            currentTotal += theoreticalCount * DENOMINATIONS[i];
        }

        // 第二步：微调总金额，尽可能贴近目标
        int difference = currentTotal - targetAmount;
        int smallestIdx = DENOMINATIONS.length - 1;
        int smallestDenom = DENOMINATIONS[smallestIdx];

        while (difference != 0) {
            if (difference > 0) {
                // 总金额超目标，先减少最小面额张数
                if (counts[smallestIdx] > 0) {
                    counts[smallestIdx]--;
                    currentTotal -= smallestDenom;
                    difference--;
                } else {
                    // 最小面额没张数了，尝试调整上一个面额（这里以$5为例）
                    int prevIdx = smallestIdx - 1;
                    if (prevIdx >= 0 && counts[prevIdx] > 0) {
                        counts[prevIdx]--;
                        currentTotal -= DENOMINATIONS[prevIdx];
                        difference -= DENOMINATIONS[prevIdx];
                    } else {
                        // 极端情况无法调整，直接退出
                        break;
                    }
                }
            } else {
                // 总金额不足，增加最小面额张数
                counts[smallestIdx]++;
                currentTotal += smallestDenom;
                difference++;
            }
        }

        // 输出结果
        System.out.println("目标金额: $" + targetAmount);
        System.out.println("实际总金额: $" + currentTotal);
        System.out.println("各面额分配详情：");
        for (int i = 0; i < DENOMINATIONS.length; i++) {
            int amount = counts[i] * DENOMINATIONS[i];
            double actualRatio = new BigDecimal(amount)
                    .divide(new BigDecimal(currentTotal), 4, RoundingMode.HALF_UP)
                    .doubleValue() * 100;
            System.out.printf("$%d: %d 张，金额 $%d，占比 %.2f%% (目标 %.0f%%)%n",
                    DENOMINATIONS[i], counts[i], amount, actualRatio, TARGET_RATIOS[i] * 100);
        }
    }

    public static void main(String[] args) {
        // 测试示例：目标金额$27869
        allocateCash(27869);
    }
}

代码说明 #

1. 按面额从大到小排序，优先处理大面额，保证占比精度。
2. 用四舍五入计算基础张数，尽可能贴近理论占比对应的金额。
3. 用最小面额微调总金额，最大程度保留大面额的占比合理性。
4. 输出时会对比实际占比和目标占比，方便验证结果。

递归实现思路（如果坚持用递归） #

如果一定要用递归，可以从最大面额开始，在理论张数的小范围内（比如±2）尝试不同张数，递归处理下一个面额，最后筛选出总金额最接近目标且占比偏差最小的组合。伪代码如下：

// 全局变量存储最优解
bestCounts = []
bestTotal = 0
minDifference = 无穷大
bestRatioDeviation = 无穷大

function recursiveAllocate(index, currentCounts, currentTotal, target):
    if index == 4:  // 所有面额处理完毕
        difference = abs(currentTotal - target)
        // 计算当前组合的占比偏差总和
        ratioDeviation = 0
        for i from 0 to 3:
            actualRatio = (currentCounts[i] * DENOMINATIONS[i]) / currentTotal
            ratioDeviation += abs(actualRatio - TARGET_RATIOS[i])
        // 更新最优解：优先选差值小的，差值相同则选占比偏差小的
        if difference < minDifference or (difference == minDifference and ratioDeviation < bestRatioDeviation):
            minDifference = difference
            bestCounts = copy(currentCounts)
            bestTotal = currentTotal
            bestRatioDeviation = ratioDeviation
        return
    // 计算当前面额的理论张数
    theoreticalAmount = target * TARGET_RATIOS[index]
    theoreticalCount = round(theoreticalAmount / DENOMINATIONS[index])
    // 在理论张数上下尝试小范围，避免遍历过多
    for count in [theoreticalCount-2, theoreticalCount-1, theoreticalCount, theoreticalCount+1, theoreticalCount+2]:
        if count < 0:
            continue
        newTotal = currentTotal + count * DENOMINATIONS[index]
        currentCounts[index] = count
        recursiveAllocate(index+1, currentCounts, newTotal, target)

这种递归方法通过限制张数尝试范围来控制计算量，适合面额种类少的场景。

内容的提问来源于stack exchange，提问作者Dreamer