백준 : 12865 - 평범한 배낭

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

냅색 알고리즘을 이용하는 문제였다....

근데 처음에 생각하지 못하고 삽질삽질하다가,,, 냅색알고리즘도 야매로 구현하다가,,,

수많은 삽질끝에 해결했다!

 

작년 알고리즘 수업때 배운 기억이 있는데,,, 잠깐 언급하고 지나갔나? 자료를 찾을 수 없었다.

이 기회에 DP공부를 좀 확실히 해야겠다.

---

냅색 알고리즘의 기본문제?같은 느낌이다.

알고만 있으면 바로 풀 수 있는!!

그래서,,,,

따로 정리해서 링크로 추가해두려고 한다ㅎ

>>> <<<

 

---

1. 메모리초과

=> 냅색 알고리즘을 생각하지 못하고, 완전탐색으로 풀었다!

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int n, k;
vector<pair<int, int>> weight_values;
vector<vector<int>> how_bags;

void choose(int index, vector<int> now_bags) {
	if (index == n) {
		how_bags.push_back(now_bags);
		return;
	}
	choose(index + 1, now_bags);
	now_bags.push_back(index);
	choose(index + 1, now_bags);
}



int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		weight_values.push_back({ a, b });
	}

	choose(0, {});

	int result = INT_MIN;

	for (int i = 0; i < how_bags.size(); i++) {
		vector<int> now_bags = how_bags[i];
		int weight_sum = 0;
		int value_sum = 0;
		for (int j = 0; j < now_bags.size(); j++) {
			weight_sum += weight_values[now_bags[j]].first;
			value_sum += weight_values[now_bags[j]].second;
		}
		if (weight_sum <= k) {
			result = max(result, value_sum);
		}
	}

	if (result == INT_MIN) {
		result = 0;
	}


	cout << result;


	return 0;
}

---

2. 냅색 알고리즘 도입 => 86%를 넘지 못함,,

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

int n, k;
vector<pair<int, int>> weight_values;
vector<vector<int>> dp;

bool cmp(pair<int, int> a, pair<int, int> b) {
	return a.first < b.first;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> k;
	dp = vector<vector<int>>(n, vector<int>(k, 0));
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		weight_values.push_back({ a, b });
	}

	sort(weight_values.begin(), weight_values.end(), cmp);

	// 확인할 물건의 index : 0
	for (int i = 0; i < k; i++) {
		if (i + 1 >= weight_values[0].first) {
			dp[0][i] = weight_values[0].second;
		}
		
	}

	for (int j = 0; j < k; j++) {
		if (j + 1 > weight_values[0].first) {
			dp[0][j] = weight_values[0].second;
		}
		for (int i = 1; i < n; i++) {
			// 무게 : j+1까지
			// 확인할 물건 : i
			if (j + 1 > weight_values[i].first) {
				// 넣을 수 있음
				dp[i][j] = max(dp[i - 1][j], dp[i-1][j - weight_values[i].first] + weight_values[i].second);
			}
			else {
				dp[i][j] = dp[i - 1][j];
			}
		}
	}
	
	

	cout << dp[n - 1][k - 1];

	return 0;
}

j부터 반복을 시작하는 이유는, 특정 무게에서 물건을 하나씩 넣어보는 동작을 해야하기 때문이었다.

(i번째 물건을 넣기 위해, 그 이전 i-1번째 물건까지의 기록을 바탕으로 추가해야 하므로)

=> 반복이 반대로 들어가면, 개수에 맞게 무개를 증가시킨다 == 내 머릿속으로는 반복이 3번들어가야 할것같았다..

 

이렇게 보니, 애초에 dp를 선언할 때 [물건개수][무게] 가 아니라 [무게][물건개수]로 선언했으면 더 효율적이었을것같다..만 통과했으니까/.ㅎㅎ

 

이 코드가 통과하지 못한이유는...

---

3. 무게비교

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

int n, k;
vector<pair<int, int>> weight_values;
vector<vector<int>> dp;

bool cmp(pair<int, int> a, pair<int, int> b) {
	return a.first < b.first;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> k;
	dp = vector<vector<int>>(n+1, vector<int>(k+1, 0));
	weight_values.push_back({ 0, 0 });
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		weight_values.push_back({ a, b });
	}

	//sort(weight_values.begin(), weight_values.end(), cmp);

	

	for (int j = 0; j <= k; j++) {
		for (int i = 1; i <= n; i++) {
			// 무게 : j까지
			// 확인할 물건 : i
			if (j >= weight_values[i].first) {
				// 넣을 수 있음
				dp[i][j] = max(dp[i - 1][j], dp[i-1][j - weight_values[i].first] + weight_values[i].second);
			}
			else {
				dp[i][j] = dp[i - 1][j];
			}
			//cout << i << ", "<<j << " : "<< dp[i][j] << endl;
		}
	}
	
	

	cout << dp[n][k];

	return 0;
}

무게 비교할 때 등호를 넣어줘야했다!.....

"이하"일 때 담을 수 있으니까.. 딱 맞을때도 담을수 있다.ㅎㅎ.ㅎ.ㅎ...