13) 백준 12865 - 평범한 배낭

12865번: 평범한 배낭 (acmicpc.net)

12865번: 평범한 배낭

---

혼자 해보려고 시도 했다가 시간만 많이 쓴 문제

// DP - Knapsack
#include <bits/stdc++.h>

using namespace std;


int bag[101][100001] = {0, };
pair<int, int> object[101];

int main(void) {
	
	int N, K, W, V;
	cin >> N >> K;
	
	for(int i = 1; i <= N; i++) {
		cin >> W >> V;
		object[i] = make_pair(W, V);
	}
	
	for(int i = 1; i <= N; i++) {
		for(int j = 1; j <= K; j++) {
			if(object[i].first > j)
				bag[i][j] = bag[i-1][j];
			else {
				bag[i][j] = max(bag[i-1][j], bag[i-1][j-object[i].first] + object[i].second);
			}
		}
	}
	
	cout << bag[N][K] << endl;
	
	return 0;
}

 

점화식 이었던 문제로 Knapsack 알고리즘을 사용했다.

 

문제가 계속 안풀려서 찾아본 문제. (계속 시간초과가 걸렸다.)

 

이유는 백트래킹을 사용했기 때문.

 

// Backtracking
#include <bits/stdc++.h>

using namespace std;

int N, K;
int highest_sum = 0;
pair<int, int> bag[100];
int check[100] = {0, };

void dp(int sum_bag, int sum_price, int start_point) {
	if(start_point == N) {
		return;
	}
	for(int i = start_point; i < N; i++) {
		if(check[i] == 0) {
			check[i] = 1;
			if(sum_bag + bag[i].first <= K) {
				sum_bag += bag[i].first;
				sum_price += bag[i].second;
				
				if(highest_sum <= sum_price) {
					highest_sum = sum_price;
					dp(sum_bag, sum_price, i+1);
				}
				else {
					dp(sum_bag, sum_price, i+1);
				}
				sum_bag -= bag[i].first;
				sum_price -= bag[i].second;
			}
			else {
				check[i] = 0;
				return;
			}
			check[i] = 0;
		}
	}
}

int main(void) {	
	int W, V;
	cin >> N >> K;
	
	for(int i = 0; i < N; i++) {
		cin >> W >> V;
		bag[i] = make_pair(W, V);
	}
	
	sort(bag, bag+N);
	
	int sum_bag = 0;
	int sum_price = 0;
	
	dp(sum_bag, sum_price, 0);
	
	cout << highest_sum << endl;
	
}

 

Knapsack의 알고리즘은 이미 구해놓은 값들을 재활용해서 쓰는 반면 백트래킹은 모든 값들을 가지고 체크하기 때문이다.