项目派遣问题-回溯法

问题描述

某公司有n名员工，第i名员工具有的能力可以用一个正整数 $a_i$ 描述，成为员工的能力值。现在，公司有一个项目需要交给恰好 $\left \lceil \frac{n}{2} \right \rceil$ 名员工负责。为了保证项目能顺利进行，要求负责项目的所有员工能力值之和大于等于x。

公司希望你可以帮忙求出，有多少种不同的派遣员工来负责这个项目的方案。

上文中， $\left \lceil x \right \rceil$ 表示大于等于x的最小整数。例如 $\left \lceil 4 \right \rceil=4 ,\left \lceil 4.2 \right \rceil =5$ 。认为两个方案不同，当且仅当粗壮乃一名员工在一种方案中负责该项目，而在另一种方案中不负责。

输入描述

输入包含多组数据，输入第一行包含一个整数( $1\le T\le 10$ ),表示数据组数。

接下来2T行，每两行描述了一组数据。

每组数据第一行包含两个正整数n( $1\le n\le 16$ )和x( $1\le x\le 2*10^4$ ),分别表示公司的员工总数和项目对负责员工能力值之和的要求。

每组数据第二行包含n个整数，第i个整数表示第i名员工的能力值 $a_i$ ( $1\le a_i\le 10^3$ )

对于100%的数据，满足 $1\le n \le 16,1\le x\le 2*10^4,1\le T\le 10,1\le a_i\le 10^3$

输出描述

输出包含T行，对于每组数据输出一行一个整数，表示可行的派遣方案数。

样例输入

3
5 10
3 2 3 4 5
3 3
1 1 1
10 10
3 1 2 6 5 4 2 9 12 7

样例输出

7
0
252

提示

对于样例的额第一组数据，在所有选择3名员工的方案中，有3中选择方案不可行：

选择第1、2、3名员工

选择第1、2、4名员工

选择第2、3、4名员工

其余7种方案均可行，因此答案为7.

对于样例的第二组数据，所有选择2名员工的方案军不可行，因此答案为0.

解题思路

其实仔细观察就是给你个数字target，再给你个数组，选取n个数，这n个数之和大于等于target就行，然后算满足这样的有多少种方案，我们可以想到回溯法，选或者不选当前数字。

代码实现

public class Solution {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int T=scan.nextInt();
        for (int t = 0; t < T; t++) {
            int n=scan.nextInt();//员工总数
            int x=scan.nextInt();//项目对员工能力值之和的要求
            int[] ability=new int[n];
            for (int i = 0; i < n; i++) {
                ability[i]=scan.nextInt();
            }
            int half=(int)Math.ceil(n/2.0);   //需要派遣的员工数量
            int count=countSolutions(ability,x,0,half,0);
            System.out.println(count);
        }
    }
    //回溯法
    public static int countSolutions(int[] ability,int targetSum,int index,int remaining,int currentSum){
       if(remaining==0){
           return (currentSum>=targetSum)?1:0;
       }
       if(index>=ability.length){
           return 0;
       }
       //选择当前员工或不选择当前员工
       int count=0;
       count+=countSolutions(ability,targetSum,index+1,remaining-1,currentSum+ability[index]);
       count+=countSolutions(ability,targetSum,index+1,remaining,currentSum);
       return count;
    }
}