贪婪算法 选数问题

选数问题

问题描述

Given n positive numbers, ZJM can select exactly K of them that sums to S. Now ZJM wonders how many ways to get it!
_______________________________________________________
给出n个正数，选出其中K个，使其总和为S —— 问共有多少种方法？

Input

The first line, an integer T ≤ 100, indicates the number of test cases. For each case, there are two lines. The first line, three integers indicate n, K and S. The second line, n integers indicate the positive numbers.
Remember that k ≤ n ≤ 16 and all numbers can be stored in 32-bit integer. 
_______________________________________________________
第一行，一个整数 T (T ≤ 100), 表示数据组数。
对于每组数据，接下来两行，第一行：3个整数 n, K, S。第二行：n 个正整数。
k ≤ n ≤ 16。所有数都能存在32位寄存器中。

Output

For each case, an integer indicate the answer in a independent line.
____________________________
对于每组数据，独立一行输出答案。

Sample

input: 
1
10 3 10
1 2 3 4 5 6 7 8 9 10

output:
4

Limitation

Time limit		3000 ms
Memory limit	262144 kB

解题思路

组合问题。
n个选出K个，共有${n \choose K}$种组合，然后从这些组合中选出符合数之和为S的情况即可。
由于这是A题，暴力求解，不要太在意时间复杂度🙄。
利用递归，每次枚举一个数加入到res数组中，递归之后由于每次加入的数不同，会产生多个分支。在这些分支上最终生成的数组就是这n个数的所有含有K个元素的子集，对这些子集元素求和判断是否为S即可。

源代码

#include <iostream>
#include <vector>
using namespace std;

int total = 0;

/*贪婪算法 每次都把可行的数加入到res数组中，加入的数达到n个后，求和*/
void greedy(int* arr, int n, int K, int S, int i, vector<int>& res) {
	if (i == n) {//总的n个数，已经全部考虑了
		if (res.size() == K) {//新数组已经达到要求的K个数时
			int sum = 0;
			for (int j = 0; j != K; j++)
				sum += res.at(j);//求这些数的和
			if (sum == S)//该情况可行 达成目标
				total++;//计数 + 1
		}
		return;
	}
    //递归枚举每个数，生成子集
	greedy(arr, n, K, S, i + 1, res);
	res.push_back(arr[i]);
	greedy(arr, n, K, S, i + 1, res);
	res.pop_back();
}

int main() {
	int T;
	cin >> T;
	for (int i = 0; i < T; i++) {
		unsigned int n, K, S;
		cin >> n >> K >> S;//n个数 选出K个 其和为S
		int* arr = new int[n + 5];
		for (int j = 0; j < n; j++)
			cin >> arr[j];
		total = 0;//共有total种方案
		vector<int> v;
		greedy(arr, n, K, S, 0, v);
		cout << total << endl;
	}

	return 0;
}