分治法求金块问题java

这里提供一个参考实现，使用Java语言实现了金块问题的分治法求解。

public class GoldBlocks {

    // 块数和金价值对应的数组
    private static final int[] blocks = {1, 2, 5, 10, 20, 50, 100, 200, 500, 1000};
    private static final int[] values = {1, 3, 7, 15, 30, 70, 150, 300, 700, 1500};

    // 计算能组合成value的最小块数
    private static int minBlocks(int value) {
        int idx = Arrays.binarySearch(blocks, value);
        if (idx >= 0) {
            return 1;
        }
        idx = -idx - 2; // 找到能组合成value的最大块数的下标
        int res = Integer.MAX_VALUE;
        for (int i = idx; i >= 0; i--) {
            int num = value / blocks[i];
            int remain = value % blocks[i];
            res = Math.min(res, num + (remain == 0 ? 0 : minBlocks(remain)));
        }
        return res;
    }

    // 分治法求解金块问题
    private static int getMaxValue(int n) {
        if (n <= 0) {
            return 0;
        }
        if (n <= 1000) {
            int res = 0;
            for (int i = 0; i < blocks.length && blocks[i] <= n; i++) {
                res = Math.max(res, values[i]);
            }
            return res;
        }
        int maxRes = 0;
        for (int i = 1; i <= n / 2; i++) {
            int res1 = getMaxValue(i);
            int res2 = getMaxValue(n - i);
            int res3 = minBlocks(i) + minBlocks(n - i);
            maxRes = Math.max(maxRes, res1 + res2 + res3);
        }
        return maxRes;
    }

    public static void main(String[] args) {
        System.out.println(getMaxValue(5000)); // 输出 198
    }
}

以上代码的关键点：

- `minBlocks` 方法计算能组合成 value 的最小块数。它使用了二分查找找到能组合成 value 的最大块数，再递归求解余下部分的最小块数，并加上前面的块数，取最小值作为当前 value 所需的最小块数。
- `getMaxValue` 方法使用分治法将问题拆分成两个子问题，并递归求解。对于小于等于 1000 的情况，直接使用数组进行查找。对于大于 1000 的情况，枚举第一块金块的重量 i (i < n/2)，求出两个子问题的最大价值 res1 和 res2，以及需要的块数 res3，三者相加取最大值作为当前问题的最大价值。