代币的最佳组合

上一篇写了关于下单优惠的计算,项目迭代了几期,产品又提出要在下单后支付前还要有新的优惠措施,以一种不同面值的代币形式.买家可以选择不同面值的组合减免支付金额.

问题描述

当用户下单后进入支付页面,系统优先计算出最划算的组合,供给用户选择.故实际付款金额=下单金额-代币组合值,代币不限数量,所以组合会有很多组合.例如有10,10,45,50,100的面值的代币,下单金额为75,最优组合为10,10,50.

解决思路

全排列方式

既然是多种组合,当我们使用迭代排列出全部组合,然后找出最优的解,但是这样的暴力穷举法,时间复杂度和空间复杂度都是很大,移动端性能本身就较弱,这样计算量和存储无法负担,并且计算时间长,没有现实意义.在测试用例中当有24个数字时, fullCombination 方法耗时平均15s左右,并且这是在 PC 执行的结果.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public List<List<Coin>> fullCombination(List<Coin> lstSource) {
int n = lstSource.size();
int max = 1 << n;//2的n次方
List<List<Coin>> lstResult = new ArrayList<>();
for (int i = 0; i < max; i++) {
List<Coin> lstTemp = new ArrayList<>();
for (int j = 0; j < n; j++) {
//i除以2的j次方
if ((i >> j & 1) > 0) {
lstTemp.add(lstSource.get(j));
}
}
lstResult.add(lstTemp);
}
lstResult.remove(0);
return lstResult;
}

回溯算法

我们可以把这个问题抽象成:给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合.candidates 中的每个数字在每个组合中只能使用一次.这个就是 LeetCode 中的组合总和II的题目,我们的需求完全一样,只需要小调整就可以使用,并且在时间复杂度O(n!)内,实际应用中可完全接受.使用上面的测试用例,得到最后的最优组合只需要20ms左右.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
public class Coin {
public String id;
/**
* 面值
*/
public double denomination;
}
/**
* 获取最优组合
*
* @param target 下单金额
* @param coins 所有代币
* @return 最优组合中的代币
*/
private List<Coin> getBestCombination(double target, List<Coin> coins) {
List<Coin> result = new ArrayList<>(5);
List<ArrayList<Coin>> combinations = new ArrayList<>(10);
//所有代币组合
combinations = combinationSum(coins, target, combinations);

TreeMap<Integer, List<Coin>> lastResult = new TreeMap<>();
//根据组合中的代币 计算出总和按升序排列
for (List<Coin> arrays : combinations) {
int temp = 0;
for (Coin c : arrays) {
temp += c.denomination;
}
lastResult.put(temp, arrays);
}
//获取最后一个组合即为最优组合
result.addAll(lastResult.lastEntry().getValue());
return result;
}

private List<ArrayList<Coin>> combinationSum(List<Coin> coins,
double target,
List<ArrayList<Coin>> result) {
List<ArrayList<Coin>> res = new ArrayList<>(10);
if (coins == null || coins.size() == 0) return new ArrayList<>(1);
List<Coin> realCoins = new ArrayList<>(coins.size());
for (Coin c : coins) {
if (c.denomination <= target) {
realCoins.add(c);
}
}
Collections.sort(realCoins, new Comparator<Coin>() {
@Override
public int compare(Coin c1, Coin c2) {
return Double.compare(c1.denomination, c2.denomination);
}
});
return dfs(realCoins, 0, target, new ArrayList<Coin>(10), res, result);
}

private List<ArrayList<Coin>> dfs(List<Coin> candidates,
int startIndex,
double target,
List<Coin> combination,
List<ArrayList<Coin>> res, List<ArrayList<Coin>> result) {
//存储所有组合结果
result.add(new ArrayList<>(combination));

if (target == 0) {
res.add(new ArrayList<>(combination));
return result;
}

for (int i = startIndex, size = candidates.size(); i < size; i++) {
if (i != startIndex && candidates.get(i).denomination == candidates.get(i - 1).denomination) {
continue;
}
if (target < candidates.get(i).denomination) {
break;
}
combination.add(candidates.get(i));
dfs(candidates, i + 1, target - candidates.get(i).denomination, combination, res, result);
combination.remove(combination.size() - 1);
}
return result;
}

项目地址 包含两种方法的所有代码和测试用例.

参考

组合总和 II LeetCode
浅谈回溯与深度优先搜索
组合总和 II 解法