Di chuyen bo

Level 3
Di chuyển bò
Toản có một đàn bò, Toản muốn di chuyển đàn bò đi nơi khác bằng một chiếc xe tải có tải trọng (300kg < C < 3000kg).  Anh ta muốn di chuyển được khối lượng lớn nhất mà không quá trọng tải của xe. Cho số lượng bò là N (5 < N < 16) và khối lượng của mỗi con. Xác định khối lượng tối đa mà có thể di chuyển được.

Input

Dòng đầu tiên số T là số trường hợp test.

Với mỗi trường hợp dòng đầu gồm 2 số M, N là trọng tải của xe và số bò.

Dòng thứ 2 là khối lượng của các con bò.

 

Output

Với mỗi trường hợp gồm “#” và số trường hợp test và kết quả trường hợp đó.

 

Sample

 

Input

2

366 5

139 105 126 139 114

315 5

112 133 123 115 126

 

Output

#1 358

#2 259
 
#1 366
#2 264
#3 397
#4 297
#5 772
#6 785
#7 611
#8 553
#9 1098
#10 949
#11 1023
#12 1011
#13 1287
#14 1372
#15 1310
#16 1540
#17 1029
#18 543
#19 1348
#20 1649

20
372 5 
133 111 144 103 130 
314 5 
130 131 114 133 125 
398 5 
111 139 100 128 147 
331 5 
137 149 139 148 124 
840 6 
118 120 147 120 124 143 
786 8 
132 137 128 132 109 134 133 144 
889 5 
117 123 108 136 127 
572 5 
105 118 117 107 106 
1433 9 
141 117 116 114 147 102 117 130 114 
1246 8 
102 114 100 139 133 113 143 105 
1291 8 
114 121 130 129 149 140 138 102 
1033 10 
107 110 105 116 145 133 148 100 126 126 
1587 11 
104 119 145 129 109 134 115 125 101 105 101 
1783 11 
147 101 140 142 111 127 127 122 125 111 119 
1812 11 
102 130 126 113 148 111 142 103 109 114 112 
1616 12 
149 103 122 130 135 143 138 115 113 131 117 144 
1029 14 
104 103 117 139 114 124 119 118 121 128 103 106 126 105 
543 14 
100 130 123 147 117 111 115 128 114 147 138 105 105 135 
1348 14 
144 120 143 105 125 137 135 143 102 126 147 144 103 147 
1890 13 
147 106 138 146 147 128 106 118 143 107 103 133 127

#include <iostream>
using namespace std;


int T, m, n, result;
int a[18], binary[18];

void generateBinary(int index, int value){
	binary[index] = value;
	if(index == n-1){
		int sum = 0;
		for(int i = 0; i < n; i++){
			sum += (binary[i] * a[i]);
		}
		if(sum <= m && sum > result) result = sum;
	} else{
		generateBinary(index + 1, 0);
		generateBinary(index + 1, 1);
	}

}

int main(){
	freopen("input.txt", "r", stdin);
	cin >> T;
	
	for(int tc = 1; tc <= T; tc++){
		// Input
		cin >> m >> n;
		for(int i = 0; i < n; i++) cin >> a[i];

		// Initial
		result = 0;
		for(int i = 0; i < n; i++) binary[i] = 0;
		
		generateBinary(0, 1);
		generateBinary(0, 0);

		// Output
		cout << "#" << tc << " " << result << endl;;
	}

	return 0;
}#include <iostream>
using namespace std;


int T, m, n, result;
int a[18], binary[18];

void generateBinary(int index, int value){
	binary[index] = value;
	if(index == n-1){
		int sum = 0;
		for(int i = 0; i < n; i++){
			sum += (binary[i] * a[i]);
		}
		if(sum <= m && sum > result) result = sum;
	} else{
		generateBinary(index + 1, 0);
		generateBinary(index + 1, 1);
	}

}

int main(){
	freopen("input.txt", "r", stdin);
	cin >> T;
	
	for(int tc = 1; tc <= T; tc++){
		// Input
		cin >> m >> n;
		for(int i = 0; i < n; i++) cin >> a[i];

		// Initial
		result = 0;
		for(int i = 0; i < n; i++) binary[i] = 0;
		
		generateBinary(0, 1);
		generateBinary(0, 0);

		// Output
		cout << "#" << tc << " " << result << endl;;
	}

	return 0;
}