[JAVA] Knapsack 알고리즘

Knapsack 알고리즘 이란?

• Knapsack은 배낭이란 뜻으로, Knapsack 알고리즘은 배낭 알고리즘 이라고도 불림
• Knapsack 알고리즘은 DP의 일종으로 배낭 채우기 문제에서 유래되었음
• 배낭 채우기 문제란 배낭의 크기 k와 n개의 물건 각각의 무게와 가치가 주어졌을 때, 배낭에 넣은 물건들의 최대 가치의 합을 구하는 문제
• ex) 무게가 7까지 담을 수 있는 배낭이 있고, 5개의 물건의 무게와 가치가 아래와 같다고 생각해 보자
  • 물건 1 : 무게 3, 가치 8
  • 물건 2 : 무게 1, 가치 5
  • 물건 3 : 무게 2, 가치 7
  • 물건 4 : 무게 2, 가치 2
  • 물건 5 : 무게 2, 가치 6
• 이 때, 가방에 넣을 수 있는 최대 가치를 구해보자
• 만약 1번 물건(3, 8)만 있었다고 가정해보면 DP 테이블은 아래와 같이 채워짐

• 이 상황에서 2번 물건(1, 5)가 추가 된다면 아래와 같이 채워짐

• dp[ 2 ][ 4 ] = Math.max{ dp[ 1 ][ 4 ], dp[ 1 ][ 4 - 1(2번 물건 무게) ] + 5(2번 물건 가치) }
  • dp[ 1 ][ 4 ] : 2번 물건을 포함하지 않은 배낭이 4일 때의 최대값
  • dp[ 1 ][ 4 - 1 ] + 5 : 2번 물건을 포함한 배낭이 4일 때의 최댓값

dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - things[i].w] + things[i].v);

• 이와 같은 방식으로 물건의 개수( n ) * 배낭 무게( k ) 2차원 DP를 진행하면 정답을 구할 수 있음

구현

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

12865번: 평범한 배낭

• 이 문제를 Knapsack 알고리즘을 통해 해결하면서 구현해봄

코드

import java.util.Scanner;

public class p12865 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();   // 물건 개수
        int k = sc.nextInt();   // 가방 크기

        Thing[] things = new Thing[n + 1];
        for(int i = 1 ; i <= n ; i ++) {
            things[i] = new Thing(sc.nextInt(), sc.nextInt());
        }

        int[][] dp = new int[n + 1][k + 1];
        for(int i = 1 ; i <= n ; i ++) {
            for(int j = 1 ; j <= k ; j ++) {
                if(j < things[i].weight) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - things[i].weight] + things[i].value);
                }
            }
        }

        System.out.println(dp[n][k]);
    }

    static class Thing {
        int weight, value;

        public Thing(int weight, int value) {
            this.weight = weight;
            this.value = value;
        }
    }
}