백준 19942 / CPP

https://www.acmicpc.net/problem/19942

이 문제의 경우 비트 마스킹 문제 였다 정확히는 비트마스킹을 이용한 브루트 포스가 맞다
비트마스킹을 통해 모든 경우의 수에 대해 구한후 푸는 문제였다
각  재료의 사용 여부를 나타내는 표를 한번 그려보겠다

그릴시 이러한 이미지  가  만들어  진다 즉 사용하면 1 사용하지 않으면 0  위에표는 2번 4번을 사용하고 5개의 재료로 만들수 있는 32개의 경우의 수중 10번 조합이라고 보면된다 그이유는 이진수 01010은 10이기 때문이다
여기 까지 구했으면 우리는 각 조합마다의 재료의 합과 비용의 합을 구한다

그 다음 조건을 만족했을 경우 Map 에다가 가격과 해당 가격에 대한 조합들을  저장해준다 그후 만족한 조합의 최소 가격의 map에서 vector에 조합들이 저장되어 있을 것이고 해당 조합을 오름 차순으로 정렬하여 출력해 주면 된다

#include<bitset>
#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#define INF 200000000
using namespace std;
int n;
map<int, vector<vector<int>>> nutritient_map;
int mp_sum, mf_sum, ms_sum, mv_sum, mc_sum;
int costMax = INF;
struct nutritient {
	int p, f, s, v, c;
};
int main() {
	int mp, mf, ms, mv;
	cin >> n >> mp >> mf >> ms >> mv;
	nutritient arr[15];
	for (int i = 0; i < n; i++) {
		cin >> arr[i].p >> arr[i].f >> arr[i].s >> arr[i].v >> arr[i].c;
	}
	for (int i = 1; i <  (1 << n); i++) {
		mp_sum = mf_sum = ms_sum = mv_sum = mc_sum = 0;
		vector<int> v;
		for (int j = 0; j < n; j++) {
			if (i & (1 << j)) {
				mp_sum += arr[j].p;
				mf_sum += arr[j].f;
				ms_sum += arr[j].s;
				mv_sum += arr[j].v;
				mc_sum += arr[j].c;
				v.push_back(j + 1);
			}
		}

		if (mp_sum >= mp && mf_sum >= mf && ms_sum >= ms && mv_sum >= mv) {
			if (costMax >= mc_sum) {
				costMax = mc_sum;
				nutritient_map[costMax].push_back(v);
			}
		}
	}
	if (costMax == INF) {
		cout << -1 << endl;
	}
	else {
		cout << costMax << endl;
		sort(nutritient_map[costMax].begin(), nutritient_map[costMax].end());
		for (int i : nutritient_map[costMax][0]) {
			cout << i << " ";
		}
	}
}