Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
769 B
3
Indexable
Never
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;

int nTestcase, target, N, sum, maxSum;
int kilo[17];

void backtrack(int start) {
	if (start == N) {
		return;
	}
	for (int i = 0; i < 2; i++) {
		if (i == 1 && sum + kilo[start] <= target) {
			sum += kilo[start];
			maxSum = maxSum > sum ? maxSum : sum;
			backtrack(start + 1);
			sum -= kilo[start];
		}
		else {
			backtrack(start + 1);
		}
	}
}

int main() {
	freopen("input.txt","r",stdin);
	cin >> nTestcase;
	for (int testcase = 1; testcase <= nTestcase; testcase++) {
		cin >> target >> N;
		for (int i = 0; i < N; i++) {
			cin >> kilo[i];
		}
		sum = maxSum = 0;
		backtrack(0);
		cout << "#" << testcase << " " << maxSum << endl;
	}	
	return 0;
}