UVa 624 CD

想法：
    在小於等於限制的情況下一直遞迴找能放入的數字，並不斷刷新Maxsum(最接近限制的和)，詳細看底下。

	#include <cstdio>
	#include <vector>
	using namespace std;
	int track[21];
	int N, T; // T is number of tracks
	vector<int> Container; // 遞迴時暫存track
	vector<int> Ans;
	int Maxsum;
	void combination(int pos, int sum);
	int main()
	{
	while (scanf("%d %d", &N, &T) != EOF) {
	for (int i = 0; i < T; ++i)
	scanf("%d", &track[i]);
	Container.clear();
	Maxsum = 0;
	combination(0, 0);
	int sum = 0;
	for (int n : Ans) {
	printf("%d ", n);
	sum += n;
	}
	printf("sum:%d\n", sum);
	}
	}
	void combination(int pos, int sum)
	{
	if (sum > Maxsum) { // 不斷刷新Maxsum,使得Maxsum更接近N
	Ans = Container;
	Maxsum = sum;
	}
	for (int i = pos; i < T; ++i) {
	if (track[i] + sum <= N) {
	sum += track[i];
	Container.push_back(track[i]);
	combination(i + 1, sum);
	sum -= track[i];
	Container.pop_back();
	}
	}
	}

view raw [UVa] 624 CD.cpp hosted with ❤ by GitHub