[BOJ/Gold 4] 백준 23061 백남이의 여행 준비(C++)

문제 링크

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

23061번: 백남이의 여행 준비

 

문제

방학을 맞은 귀여운 백남이는 여행을 떠날 준비를 하고 있다.

백남이는 여행에 필요하다고 생각하는 필수품 N개를 가지고 있다. 각 물건은 무게 W와 가치 V를 가진다. 그리고 백남이는 물건을 담을 가방 M개를 가지고 있는데, 각각의 가방은 최대 Ki만큼의 무게를 견딜 수 있다.

MBTI가 J(판단형)인 백남이는 효율성을 중요하게 여기기 때문에, 가장 효율적으로 짐을 싸지 않으면 여행을 출발할 수 없다. 백남이가 정의한 효율성은 (가방에 담긴 물건의 가치의 합) / (가방이 견딜 수 있는 최대 무게)이다.

가방과 물건의 정보가 주어졌을 때, 가장 효율적으로 짐을 싸기 위해 필요한 가방이 무엇인지 알아내자. 가방은 한 개만 선택할 수 있으며, 최적의 가방이 여러 가지라면 그중 가장 작은 번호를 출력한다.

 

입력

첫 줄에 물품의 수 N(1≤N≤100)과 가방의 수 M(1≤M≤100)가 주어진다.

두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1≤W≤100,000)와 해당 물건의 가치 V(0≤V≤1,000)가 주어진다.

그 후에는 M개의 줄에 거쳐 가방이 버틸 수 있는 최대 무게 Ki(1≤Ki≤1,000,000)가 주어진다. 가방의 번호는 1부터 M까지이다.

입력으로 주어지는 모든 수는 정수이다.

출력

한 줄에 가장 효율적으로 짐을 싸기 위해 필요한 가방의 번호를 출력한다.

예제 입력 1

5 3
6 10
10 15
5 10
7 13
4 9
20
21
22

예제 출력 1

3

 

1번 배낭이 담을 수 있는 무게는 20이고, 담을 수 있는 최대 가치는 34이므로 효율성은 1.7이다.

2번 배낭이 담을 수 있는 무게는 21이고, 담을 수 있는 최대 가치는 37이므로 효율성은 약 1.76이다.

3번 배낭이 담을 수 있는 무게는 22이고, 담을 수 있는 최대 가치는 42이므로 효율성은 약 1.9이다.

따라서 백남이가 선택해야하는 배낭은 3번 배낭이다.

알고리즘 분류

• 배낭 문제

풀이

다른 배낭 문제와 비슷하게, DP[100][1000000]이라는 2차원 배열을 선언한다. 이것은 i번째 물건까지 j만큼의 무게를 담을 수 있는 배낭에 담았을 때의 가치를 의미한다.

배낭의 무게는 0에서부터, M개의 배낭이 담을 수 있는 무게의 최댓값까지만 구하면 된다.

마지막으로 어느 배낭을 선택해야 하는 지 결정한다. 처음에는 double 자료형을 활용하여 효율성을 실제로 구했으나, 아무래도 double형의 변수를 구할 때 발생하는 약간의 오차로 인하여 오답이 발생했는지 WA를 받았다.

그래서 이 글을 참고하여 굳이 효율성을 구하지 않고 어떤 배낭을 선택해야 하는 지 결정하였다.

[백준] 23061 백남이의 여행 준비 (C++)

왼쪽 배낭의 무게를 A, 가치를 B라고 하고, 오른쪽 배낭의 무게를 C, 가치를 D라고 하면, 효율성은 B/A와 D/C일 것이지만, 반대로 A*D와 B*C를 비교하여 A*D가 더 크다면 오른쪽 배낭을 선택해야 하고, B*C가 더 크다면 왼쪽 배낭을 선택해야 하는 것이다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <ctime>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX_N 101
#define MAX_K 1000001
#define LL long long
#define INF 1e9

using namespace std;
int N, M;
int W[MAX_N], V[MAX_N], B[MAX_N];
int Most_Weight = 0;
int DP[MAX_N][MAX_K];
int Most_VA;
int Most_WE;
int Answer;

void Input() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> W[i] >> V[i];
	}
	for (int i = 1; i <= M; i++) {
		cin >> B[i];
		Most_Weight = max(Most_Weight, B[i]);
	}
}

void Settings() {
	for (int i = 1; i <= N; i++) {
		for (int j = Most_Weight; j >= 0; j--) {
			if (j - W[i] >= 0) {
				DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - W[i]] + V[i]);
			}
			else {
				DP[i][j] = DP[i - 1][j];
			}
		}
	}
	Answer = 1;
	Most_WE = B[1];
	for (int i = 1; i <= N; i++) {
		Most_VA = max(Most_VA, DP[i][B[1]]);
	}
	for (int i = 2; i <= M; i++) {
		int VA = 0;
		for (int j = 1; j <= N; j++) {
			VA = max(VA, DP[j][B[i]]);
		}
		if ((LL)Most_VA * (LL)B[i] < (LL)VA * (LL)Most_WE) {
			Most_VA = VA;
			Most_WE = B[i];
			Answer = i;
		}
	}
}

void Find_Answer() {
	cout << Answer << "\n";
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}