给定数量的1、5、10三种面值的货币,对于某个给定的总数(例如10),可以有多少种可能的组合方案。
输入样例:
5 2 1
10
解释:第一行三个数字,依次表示1、5、10三种面值货币的数量;第二行一个数字,表示给定的总数
输出样例:
3
解释:针对上面输入,10有三种组合方式:1*5+5*1,5*2,10*1
package test; import java.util.Arrays; import java.util.LinkedHashMap; import java.util.LinkedList; import java.util.List; import java.util.Map; import java.util.concurrent.atomic.AtomicInteger; /** * 给定数量的1、5、10三种面值的货币,对于某个给定的总数(例如10),可以有多少种可能的组合方案。 输入样例: 5 2 1 10 * 解释:第一行三个数字,依次表示1、5、10三种面值货币的数量;第二行一个数字,表示给定的总数 * * 输出样例: 3 解释:针对上面输入,10有三种组合方式:1*5+5*1,5*2,10*1 * * @author Administrator * */ public class TestSU2 { static final Integer[][] array = {{1, 5000}, {5, 5000}, {10, 5000}}; static final int target = 5000; public static void main(String[] args) { long start = System.currentTimeMillis(); combinationSum(Arrays.asList(array), target); long end = System.currentTimeMillis(); System.out.println("cost " + (end - start) + "ms."); } /** * combinationSum * * @param nums * @param target * @return */ public static List<Map<Integer, AtomicInteger>> combinationSum(List<Integer[]> nums, int target) { List<Map<Integer, AtomicInteger>> result = new LinkedList<>(); // 最终结果 Map<Integer, AtomicInteger> intermediate = new LinkedHashMap<>(); dfs(nums, target, 0, intermediate, result); return result; } /** * * @param nums * @param gap * @param level * @param intermediate * @param result */ private static void dfs(List<Integer[]> nums, int gap, int level, Map<Integer, AtomicInteger> intermediate, List<Map<Integer, AtomicInteger>> result) { if (gap == 0) { // 找到一个合法解 System.out.println("===================答案====================="); intermediate.entrySet().stream().filter(m -> m.getValue().get() != 0).forEach(m -> { System.out.println(String.format("面值纸币:%s, 数量:%s.", m.getKey(), m.getValue().get())); }); return; } for (int i = level; i < nums.size(); i++) { // 扩展状态 int item = nums.get(i)[0]; int limit = nums.get(i)[1]; AtomicInteger count = intermediate.get(item); // System.out.println("gap:" + gap + ",item:" + item + ", value:" // + String.valueOf((count == null) ? 0 : count.get())); if (((count == null) ? 0 : count.get()) >= limit) { continue; } if (gap < item) { return; // 剪枝 } if (intermediate.get(item) == null) { intermediate.put(item, new AtomicInteger(1)); } else { intermediate.get(item).incrementAndGet(); // 执行扩展动作 } dfs(nums, gap - item, i, intermediate, result); if (intermediate.get(item) != null) { intermediate.get(item).decrementAndGet(); } // 撤销动作 } } }