某公司晚上可以领20元夜宵，夜宵商品的价格有x1,x2,x3...xn共计N种（价格可能为小数），请统计出总价在19.5~20元之间的夜宵组合的数量。
使用递归可以通过深度优先遍历的方式实现所有结果的搜索，而用递归的地方就可以使用堆栈或者队列的方式来实现。由于该问题可以使用分治法进行求解，所以用ForkJoinPool可以实现一个多线程版本。
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/*
夜宵组合 回溯问题
4
2.5 7 8 12
*/
public class Main {
static final float MAX_PRICE = 20f;
static final float MIN_PRICE = 19.5f;
static int n;
static int res;
static List<Float> prices = new ArrayList<>();
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
n = Integer.parseInt(sc.nextLine());
res = 0;
String[] blocks = sc.nextLine().trim().split(" ");
for (int i = 0; i < blocks.length; i++) {
prices.add(Float.parseFloat(blocks[i]));
}
tryAdd(0, 0);
System.out.println(res);
}
}
public static void tryAdd(float price, int depth) {
for (int i = 0; price + i * prices.get(depth) <= MAX_PRICE; i++) {
float next_price = price + i * prices.get(depth);
if (depth == n - 1) {
if (next_price >= MIN_PRICE) {
res++;
}
} else {
tryAdd(next_price, depth + 1);
}
}
}
}
