배낭 문제 Knapsack🎒 - 12865번: 평범한 배낭

 

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

12865번: 평범한 배낭

▶ 유형

• S는 전체 물건들의 집합
• 각 물건은 무게를 갖고 있고, 가치를 갖고 있을 때
• 설정된 최대 무게를 넘지 않으면서 최대 가치를 가질 수 있는 물건 부분 집합 A ⊆ S을 구하는 것
• 물건을 일부분만 가져가면서 배낭을 채우는지, 무조건 해당 물건 통으로 챙겨야 하는 지에 따라서
  0-1 배낭, 부분 배낭 문제로 유형이 갈린다.

부분집합을 모두 생성해서(bruteforce) 풀 수 도 있지만 전체 물건 수 n이 커지면 시간복잡도가 터질 위험이 있다.

=> O(2^n) // 부분 집합 생성에만

n이 30만 되더라도 약 10억이라서(leaf노드 생성만) 재귀 스택이 못버텨 터져버릴 것이다. 가지치기를 쳐서 최대한 버티더라도 더 큰 n만나면 답이 없다.

▶ 전략

0-1 배낭 문제의 경우

선택 기준이 무게, 가치 두 개가 있다고 각각의 경우로 나누면, 최적해를 구할 수 없다.

• 무게 기준으로 가벼운 거 부터 담을 경우 -> 무거운 것 하나가 다른 것보다 압도적 가치를 지니면 반례가 된다.
• 가치 기준으로 높은 거 부터 담을 경우 -> 가치 높은 거 하나를 담았을 때보다, 가치 낮은거 여러개를 담았을 때가 더 합산이 높아질 수 있다.
• 무게 당 가치가 높은 거로 정렬해서 담을 경우 ->  이 경우도 무거운 것 하나가 다른 것보다 압도적 가치를 지녀버리면 반례다.

결국 동적계획법으로 해결해야되는 경우가 생긴다.

 

DP의 핵심은 이전 경우의 수가 다음 경우의 수에 사용된다는 것이다. 즉 bottom-up형식으로,  어떤 최적해는 그 이전 단계의 최적해를 항상 포함한다는 원리를 이용한 알고리즘이라고 할 수 있다.

이 방법을 이용해 0-1 배낭을 다시 쪼개보면

- i번째 물건이 배낭의 한계 무게보다 무거우면 ->
i번째 물건을 제외하고 i-1개의 물건들을 가지고 구한 전 단계의 최적값을 사용한다.

- else ->
[i번째 물건만큼의 무게를 추가할 때의 최적값에 i번째 물건의 가치를 더한 값]과
[i-1개의 물건들을 가지고 구한 전 단계의 최적값] 중 큰 것을 선택한다 -> 다익스트라랑 조금 비슷한 것 같다

그럼 살펴야될 기준이 2개니까 2차원 dp로 접근한다. 

 

즉

1. 만약 현재 물건의 무게가 배낭의 무게 한도를 초과한다면, 해당 물건은 배낭에 담을 수 없으므로 이전 상태(dp[i-1][w])를 그대로 유지하고.
2. 현재 물건을 배낭에 담을 수 있는 경우, 이전 물건을 담았을 때의 가치(dp[i-1][w])와 현재 물건을 담았을 때의 가치
   (dp[i-1][w - input[i][0]] + input[i][1])를 비교하여 더 큰 값으로 갱신한다.

import java.util.*;
import java.io.*;

public class Main {

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("res/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = Integer.parseInt(st.nextToken()); // 물품의 수
		int k = Integer.parseInt(st.nextToken()); // 최대 무게

		int[][] dp = new int[n + 1][k + 1]; // 용량이 k인 배낭이고, 각 row의 인덱스에는 해당 용량일 때의 가치값이 들어가있다.
		int[][] input = new int[n + 1][2]; // 각 물건의 0-무게, 1-가치
		for (int i = 1; i <= n; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			// i번째 물건의 무게, 가치
			int weight = Integer.parseInt(st.nextToken());
			int value = Integer.parseInt(st.nextToken());
			input[i][0] = weight;
			input[i][1] = value;
		}

		// 평범한 배낭
		for (int i = 1; i <= n; i++) {
			// N개의 배낭
			for (int w = 1; w <= k; w++) { // 최대 k 무게를 담을 때 때까지 반복한다
				if (input[i][0] > w) { // 물건을 담을 수 없는 경우다
					// 이 경우 그냥 이전 물건을 담을 상태를 넣어준다(물건 안 담을 거니까)
					dp[i][w] = dp[i - 1][w]; // 무게가 들어가는게 아니라 가치가 들어간다
				}
				else { // 물건을 담을 수 있는 경우다 
					// 이전 물건을 담은 상태가 지금 물건을 담을 경우와 비교했을 때 더 크면, 물건을 안담고 넘어간다 
					dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - input[i][0]] + input[i][1]);
				}
			}
		}
		System.out.println(dp[n][k]);
	}
}

 

dp[i][w - input[i][0]] 는 현재 물건을 담을 경우, 남은 배낭의 무게를 나타낸다.

즉, 현재 물건을 담는다고 전제를 하고, 현재 무게를 만들기 위한 이전 무게 index의 가치값이랑 현재 물건의 가치값을 더한 값을 비교해서 max값을 저장한다. 

따라서 w - input[i][0]는 현재 물건의 무게를 배낭의 총 무게 한도에서 뺀 값으로, 현재 물건을 담을 때의 남은 여유 공간을 나타낸다.

부분 배낭 문제의 경우

무게 당 가치가 높은 거로 정렬해서 담을 경우가 최적해가 된다. <- greedy가 통한다.

 

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요! 로그인 안해도 됩니다 ^_^