배낭 문제 개요

배낭 문제는 동적 프로그래밍의 대표적인 유형으로, 기술 평가에서 자주 등장하는 고난도 주제입니다. 다양한 변형이 존재하지만 01 배낭 문제는 가장 기초적이며 핵심적인 접근법을 제공합니다.

01 배낭 문제 분석

두 가지 핵심 질문에 대한 해법을 다룹니다:

1. 용량 제한 내 최대 가치 달성
2. 정확한 용량 충족 시 최대 가치 달성

용량 제한 버전

상태 정의: maxValue[i][c] = 처음 i개 물품에서 용량 c 이내로 선택 가능한 최대 가치

상태 전이:

maxValue[i][c] = max(
  maxValue[i-1][c],  // i번째 물품 미선택
  maxValue[i-1][c - size[i]] + worth[i]  // i번째 물품 선택 (c ≥ size[i] 시)
)

정확한 용량 버전

상태 정의: exactDP[i][c] = 처음 i개 물품으로 정확히 c 용량을 채웠을 때 최대 가치

초기화: exactDP[0][0] = 0, 나머지 -1 (불가능 표시)

상태 전이 (c ≥ size[i]이고 exactDP[i-1][c-size[i]] ≠ -1인 경우만 갱신)

공간 최적화 구현

2차원 배열을 1차원으로 압축하며 역방향 순회:

import java.util.Scanner;

public class Main {
    static final int MAX_ITEMS = 1010;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int itemCount = sc.nextInt(), maxCapacity = sc.nextInt();
        int[] sizes = new int[MAX_ITEMS];
        int[] worths = new int[MAX_ITEMS];
        
        for(int idx = 1; idx <= itemCount; idx++) {
            sizes[idx] = sc.nextInt(); 
            worths[idx] = sc.nextInt();
        }

        // 기본 버전
        int[] dpBasic = new int[MAX_ITEMS];
        for(int i = 1; i <= itemCount; i++) 
            for(int cap = maxCapacity; cap >= sizes[i]; cap--) 
                dpBasic[cap] = Math.max(dpBasic[cap], 
                                 dpBasic[cap - sizes[i]] + worths[i]);
        System.out.println(dpBasic[maxCapacity]);

        // 정확한 용량 버전
        int[] dpExact = new int[MAX_ITEMS];
        for(int cap = 1; cap <= maxCapacity; cap++) 
            dpExact[cap] = -1;
        
        for(int i = 1; i <= itemCount; i++)
            for(int cap = maxCapacity; cap >= sizes[i]; cap--)
                if(dpExact[cap - sizes[i]] != -1)
                    dpExact[cap] = Math.max(dpExact[cap], 
                                  dpExact[cap - sizes[i]] + worths[i]);
                    
        System.out.println(dpExact[maxCapacity] == -1 ? 0 : dpExact[maxCapacity]);
    }
}