SWEA 4168 : 삼성이의 쇼핑 ( 비트마스크 + 조합 연습 )

문제

---

 

문제 풀어보기

(로그인 후 접속 가능)

 

풀이

---

 

냅색 문제에서 비트 마스크를 사용하여 

선택한 물건들을 출력할 수 있도록 하였습니다.

 

 

 

냅색 알고리즘은 배낭문제에서 나온 기법인데

생각보다 자주 나오는 유형입니다.

 

 

 

최대의 만족도를 구하는 방법은 냅색을 이용해서

구하게 됩니다. 그리고 만족도를 인덱스로 하는 배열에

비트 마스크를 저장합니다.

 

 

 

출력 과정에서 정답이 되는 만족도에 있는

비트 마스크를 통해 어떤 옷을 선택했는지 출력합니다.

 

 

 

 

코드

---

#include <iostream>
#include <vector>
#include <queue>
#include <string>

using namespace std;

int max(int a, int b) {
	if (a > b) return a;
	else return b;
}

int T;
int ans;
int n, m;
int v[26][2];
int arr[26 * 200];

int napsack(int index, int capacity, int bit, int good) {
	arr[good] = bit;
	if (index == m) return 0;
	int temp = 0;
	if (v[index][0] <= capacity) {
		temp = napsack(index + 1, capacity - v[index][0]
			, bit | (1 << (index)), good + v[index][1]) + v[index][1];
	}
	temp = max(napsack(index + 1, capacity, bit, good), temp);
	return temp;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> T;
	int t = 1;
	while (t <= T) {
		cin >> n >> m;
		for (int i = 0; i < m; i++) {
			cin >> v[i][0] >> v[i][1];
		}

		ans = napsack(0, n, 0, 0);

		cout << "#" << t << ' ';
		for (int i = 0; i < m; i++) {
			if (arr[ans] & (1<<i)  ) {
				cout << i << ' ';
			}
		}

		cout << ans << endl;
		t++;
	}

	return 0;
}