냅색(Knapsack) 알고리즘

배낭 문제는 무게 제한이 있는 배낭에 여러 물건을 조합해 담아, 배낭이 터지지 않으면서도 얻을 수 있는 가치의 합을 최대화하는 문제이다.

무한 냅색 (Unbounded Knapsack)

같은 물건을 여러 번 넣어도 되어 DP(정방향)로 가치를 쌓아가는 문제

문제 (동전 2)

백준 2294번 동전 2

풀이

금액 k까지의 최솟값을 저장할 1차원 DP 배열을 충분히 큰 값으로 초기화하되, 0원을 만드는 동전 개수인 dp[0]은 0으로 설정한다.

이후 준비된 동전들을 하나씩 꺼내어 1원부터 k원까지 정방향으로 훑으며 점화식을 적용한다.

이때 정방향으로 루프를 도는 이유는 방금 사용한 동전을 같은 금액에서 또 사용할 수 있게 하기 위함이다.

각 금액마다 기존의 최솟값과 현재 동전을 하나 쓰고 남은 금액의 최솟값(+1)을 비교하여 더 작은 값을 선택한다.

단, 모든 계산이 끝난 후 dp[k]가 초기값 그대로라면(불가능한 경우) -1을 출력한다.

시간복잡도: 동전 종류의 개수($n$)와 목표 금액($k$)만큼 반복 → $O(n·k)$

import java.util.*;

public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int[] cost = new int[n];
		for(int i=0; i<n; i++) {
			cost[i] = sc.nextInt();
		}
		
		int[] dp = new int[k+1];
		Arrays.fill(dp, 100001);
		dp[0] = 0;
		
		for(int i=0; i<n; i++) {
			for(int j=0; j<=k; j++) {
				if(j-cost[i] >= 0) dp[j] = Math.min(dp[j], dp[j - cost[i]] + 1);
			}
		}
		
		if(dp[k] >= 100001) System.out.println(-1);
		else System.out.println(dp[k]);
	}
}

0/1 냅색 (0/1 Knapsack)

물건을 통째로 딱 하나씩만 넣을 수 있어 DP(역순)로 최적의 조합을 찾는 문제

문제 (평범한 배낭)

백준 12865번 평범한 배낭

풀이

왜 하나씩만 넣을 때는 역순일까?

예를 들면, dp[3]을 업데이트한 뒤 dp[6]을 계산할 때 방금 바뀐 dp[3]을 참조하게 되어 물건이 중복으로 들어간다.(무한 냅색)

역순으로 하면, 큰 무게부터 거꾸로 채우기 때문에 dp[6]을 계산할 때 참조하는 dp[3]은 아직 이번 물건이 반영되지 않은 순수한 이전 상태의 값이다.

시간복잡도: 물건 수(n)와 최대 무게(k)만큼 반복 → $O(n·k)$

import java.util.*;

public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		
		int[] weight = new int[n+1];
		int[] cost = new int[n+1];
		
		for(int i=1; i<=n; i++) {
			weight[i] = sc.nextInt();
			cost[i] = sc.nextInt();
		}
		
		int[] dp = new int[k+1];
		
		for(int i=1; i<=n; i++) {
			for(int j=k; j>=0; j--) {
				if(j - weight[i] >= 0) {
					dp[j] = Math.max(dp[j], dp[j - weight[i]] + cost[i]);
				}
			}
		}
		
		System.out.println(dp[k]);
	}
}

분수 냅색 (Fractional Knapsack)

물건을 가루처럼 쪼개 빈틈없이 넣을 수 있어 그리디(가성비)로 채우는 문제

분수 냅색은 물건을 쪼갤 수 있기 때문에 항상 "지금 당장 가성비가 제일 좋은 놈"부터 배낭에 때려 넣으면 무조건 최적의 답이 나온다.