[백준]12865 평범한 배낭 with Java

hyeok ryu·2023년 11월 3일

문제풀이 백준

문제풀이

목록 보기

23/154

문제

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

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

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

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

풀이

접근방법

시간제한 2초, 메모리 512MB이다.
N(1 ≤ N ≤ 100)
K(1 ≤ K ≤ 100,000)
W(1 ≤ W ≤ 100,000)
V(0 ≤ V ≤ 1,000)

유명한 Knapsack문제이다.

가장 단순한 방법을 생각해보자.

1. 하나의 물건을 가방에 넣거나 넣지 않는다.
2. 그 다음 물건을 가방에 넣거나 넣지 않는다.
...
N. N번째 물건을 가방에 넣거나 넣지 않는다.
-> 2^n의 모든 경우의 수를 계산한다.

2^100 경우의 수를 2초안에 계산 할 수 있는가?

다른 방법을 생각해보자.

방법 1.

2차원 배열을 이용해 DP로 풀어보자.

	3	4	5	6	7
물건X	0	0	0	0	0
물건1(3,6)	6	6	6	6	6
물건2(4,8)	6	8	8	8	14
물건3(5,12)	6	8	12	12	14
물건4(6,13)	6	8	12	13	14

arr[i][j] : i번째 물건까지 고려했을때, 최대 j까지의 무게를 담았을 경우의 최대 가치

- i번째 아이템을 넣는 경우 : value[i] + K[i-1][w-wt[i]]
- i번째 아이템을 넣지 않는 경우 : K[i-1][w]

반복문을 수행하며, i번째 아이템을 넣거나, 넣지 않으며 최대 j의 무게를 만들며 가치를 계산해 본다.

for (int i = 0; i <= N; ++i) { // 아이템 번호
			for (int j = 0; j <= K; --j) { // 무게
				if (i == 0 || j == 0) // 아이템 미선정 또는 배낭의 무게가 0
					dp[i][j] = 0;
				else if (weight[i - 1] <=  j) // i번째 아이템의 무게가 j 이하이다.
					// i 번째 아이템을 넣어 볼 수 있다면, 경우의 수를 따져본다.
					dp[i][j] = Math.max(value[i - 1] + dp[i - 1][j - weight[i - 1]], dp[i - 1][j]);
				else // 넣을 수 없는 경우.
					dp[i][j] = dp[i-1][j]; //
			}
		}

여기서 더욱더 최적화할 수 없을까?
꼭 이차원 배열을 사용해야할까?

개선

이전까지는 아이템과 무게의 조합을 통해서 최대가치를 구했다.
하지만, 결국 우리가 구하고자 하는 값은 최대가치 이므로, 특정 무게를 만들기 위한 최대가치만 저장해보자.

	3	4	5	6	7
물건X	0	0	0	0	0
물건1(3,6)	6	6	6	6	6
물건2(4,8)	6	8	8	8	14
물건3(5,12)	6	8	12	12	14
물건4(6,13)	6	8	12	13	14

표와 같이 구성된 배열을 갱신하는 과정에서 바로 직전의 행만 사용한다.
즉 무게가 낮은것부터 값을 채우며 이전의 계산된 값들을 활용해 최대가치를 계산해 왔다. 반대로 무게가 높은 것부터 낮은 순으로 순회하며 배열을 업데이트 하자.
( 아이템의 중복사용 방지 )

for (int i = 0; i < N; ++i) {
			for (int j = K; j >= weight[i]; --j) {
				dp[j] = Math.max(dp[j], value[i] + dp[j - weight[i]]);
			}
		}

코드

2차원 배열 이용

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	static int N, K;
	static int[] weight, value;
	static int[][] dp;

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		String[] splitedLine = in.readLine().split(" ");
		N = stoi(splitedLine[0]);
		K = stoi(splitedLine[1]);

		weight = new int[N + 1];
		value = new int[N + 1];
		dp = new int[N + 1][K + 1];

		for (int i = 0; i < N; ++i) {
			splitedLine = in.readLine().split(" ");
			weight[i] = stoi(splitedLine[0]);
			value[i] = stoi(splitedLine[1]);
		}

		for (int i = 0; i <= N; ++i) { // 아이템 번호
			for (int j = 0; j <= K; --j) { // 무게
				if (i == 0 || j == 0) // 아이템 미선정 또는 배낭의 무게가 0
					dp[i][j] = 0;
				else if (weight[i - 1] <=  j) // i번째 아이템의 무게가 j 이하이다.
					// i 번째 아이템을 넣어 볼 수 있다면, 경우의 수를 따져본다.
					dp[i][j] = Math.max(value[i - 1] + dp[i - 1][j - weight[i - 1]], dp[i - 1][j]);
				else // 넣을 수 없는 경우.
					dp[i][j] = dp[i-1][j]; //
			}
		}
		System.out.println(dp[N][K]);
	}

	private static int stoi(String s) {
		return Integer.parseInt(s);
	}
}

1차원 배열

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	static int N, K;
	static int[] weight, value, dp;

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		String[] splitedLine = in.readLine().split(" ");
		N = stoi(splitedLine[0]);
		K = stoi(splitedLine[1]);

		weight = new int[N + 1];
		value = new int[N + 1];
		dp = new int[K + 1];

		for (int i = 0; i < N; ++i) {
			splitedLine = in.readLine().split(" ");
			weight[i] = stoi(splitedLine[0]);
			value[i] = stoi(splitedLine[1]);
		}

		for (int i = 0; i < N; ++i) {
			for (int j = K; j >= weight[i]; --j) {
				dp[j] = Math.max(dp[j], value[i] + dp[j - weight[i]]);
			}
		}
		System.out.println(dp[K]);
	}

	private static int stoi(String s) {
		return Integer.parseInt(s);
	}
}