다이어트

1. "비트 마스킹"으로 모든 경우의 수를 다 구할수 있다.

2. 시간 복잡도가 그렇게 크지 않기 때문에 모든 경우의 수를 다 넣어보면서 최소의 값을 찾는다.

3. 그리고 같은 경우가 있을 수 있기 때문에 최소의 경우를 오름차순으로 출력해야한다.

   1 2 3, 1 2 4 있을 때 1 2 3 출력해야함

이전에는

#include <bits/stdc++.h>
using namespace std;
int n = 5, k = 3, a[5] = {1, 2, 3, 4, 5};
void print(vector<int> b){
for(int i : b)cout << i << " ";
cout << '\n';
}
void combi(int start, vector<int> b){
if(b.size() == k){
print(b);
return;
}

for(int i = start + 1; i < n; i++){
b.push_back(i);
combi(i, b);
b.pop_back();
}
return;
}
int main() {
vector<int> b;
combi(-1, b);
return 0;
}
/*
0 1 2
0 1 3
0 1 4
0 2 3
0 2 4
0 3 4
1 2 3
1 2 4
1 3 4
2 3 4
*/

이런식으로 조합을 구현했었다면은

모든 경우의 수를 따질때는 이제

비트마스킹으로

#include <bits/stdc++.h>
using namespace std;  
const int n = 4;
int main() 
{   
	string a[n] = {"사과", "딸기", "포도", "배"};
	for(int i = 0; i < (1 << n); i++)
    {
		string ret = "";
		for(int j = 0; j < n; j++)
        {
			if(i & (1 << j))
            {
				ret += (a[j] + " ");
			}
		}
		cout << ret << '\n';
	} 
    return 0;
} 
/*

사과 
딸기 
사과 딸기 
포도 
사과 포도 
딸기 포도 
사과 딸기 포도 
배 
사과 배 
딸기 배 
사과 딸기 배 
포도 배 
사과 포도 배 
딸기 포도 배 
사과 딸기 포도 배 
*/

이런식으로 가능하다.

cpp코드

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <math.h>
#include <map>
#include <algorithm>
using namespace std;
#define endl "\n"
const int INF = 1e9;
int n, mp, mf, ms, mv;
int b, c, d, e, ret = INF, sum;

struct A
{
	int mp, mf, ms, mv, cost;
} a[16];

map<int, vector<vector<int>>> ret_v;

int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n;
	cin >> mp >> mf >> ms >> mv;

	for (int i = 0; i < n; ++i)
	{
		cin >> a[i].mp >> a[i].mf >> a[i].ms >> a[i].mv >> a[i].cost;
	}
	for (int i = 1; i < (1 << n); ++i)
	{
		b = c = d = e = sum = 0;
		vector<int> v;
		for (int j = 0; j < n; ++j)
		{
			if (i & (1 << j))
			{ 
				v.push_back(j + 1);
				b += a[j].mp;
				c += a[j].mf;
				d += a[j].ms;
				e += a[j].mv;
				sum += a[j].cost;
			}
		}
		if (b >= mp && c >= mf && d >= ms && e >= mv)
		{
			if (ret >= sum)
			{
				ret = sum;
				ret_v[ret].push_back(v);
			}
		}
	}
	if (ret == INF) cout << -1 << endl;
	else
	{
		sort(ret_v[ret].begin(), ret_v[ret].end());
		cout << ret << endl;
		for (int a : ret_v[ret][0])
		{
			cout << a << " ";
		}
	}

	return 0;
}