Algorithm

알고리즘 - 배낭문제 알고리즘 (0-1)

youngjae-kim 2024. 6. 8. 15:41
728x90
반응형

배낭 문제 중에서도 0-1 배낭 문제에 대해서 정리

0-1 배낭문제는 물건을 쪼갤 수 없는 경우를 뜻한다.

 

배낭 문제의 전제

n개의 물건과 배낭이 있을 때, 각 물건에는 가치와 무게가 존재한다.

 

각 물건은 1개씩만 있다. 배낭에는 담을 수 있는 최대 용량이 존재한다.

 

이런 조건에서 배낭에 담을 수 있는 최대 가치의 합을 찾는 문제이다.

 

 

 

4개의 물건 배낭의 최대 가능 무게는 5kg 각 물건의 가치가 적혀 있다.

 

넣은 물건의 최대 가치를 구하는 방법을 생각할 때 다음과 같이 생각할 수 있다

 

물건을 넣을건가 말 것인가?

 

최대 M인 배낭에 무게 N인 물건을 넣으면 

 

만약 물건을 넣는다면 

  • (M - N) kg -> 물건을 넣은 경우
  • M kg -> 물건을 넣지 않은 경우

이걸 물건들마다 고민하면 된다.

 

그럼 무게 N인 물건을 뺀 나머지 공간 (M - N)을 담을 수 있는 배낭에 대해서 다시 같은 고민을 할 수 있다.

 

이를 그림으로 나타내면 다음과 같다.

 

최대 5kg 용량의 가방에서 2kg을 넣은 경우 2를 빼고 남은 3kg 공간의 배낭과 2kg 짜리 물건을 뺀 나머지 물건들에 대해서 문제를 고민하면 된다.

 

 

일반화 하기 (식 만들기)

두가지가 계속 변한다.

  1. 배낭의 무게
  2. 담을 물건의 무게와 종류

 

최대 이익[i][w] = 최대 무게가 w인 가방에서 i 번째 물건까지 넣을지 말지를 판단한 최대 가치

 

 

 

예를 들면 최대 이익[3][5]는 최대 무게가 5인 가방에서 3번째 물건까지 고려했을 때 최대 가치를 말하는 것이다

 

위 경우는 70이 최대 가치가 된다.

 

 

최대 가치 크게 2가지 경우로 나뉜다.

 

물건의 무게가 현재 고려중인 최대 최대 배낭 무게를 초과 할 때

이 경우는 배낭에 물건을 넣을 수 없다. 

따라서 물건의 최대 가치는 이전까지 넣었던 최대 가치가 된다.

dp[i][j] = dp[i-1][j];

 

물건의 무게가 현재 고려중인 최대 최대 배낭 무게를 초과하지 않을 때

여기서 또 경우가 나뉜다.

1. 물건을 넣었을 때 

dp[i][j] = dp[i - 1][j - w[i]] + v[i] // 이전까지 최대 가치 합 중 넣을 무게를 뺀 최대 가치에 현재 무게의 가치를 더해준 값이 최대 가치

 

이전까지 최대 가치 합 중 넣을 무게를 뺀 최대 가치는

그 물건의 무게 M을 뺀 (W-M) kg로 1~K 물건으로 구할 수 있는 최대 가치이다. (이게 좀 헷갈렸었다.)

2. 물건을 넣지 않을 때 

dp[i][j] = dp[i - 1][j]

 

넣지 않을 때 최대 가치는 이전 물건의 최대 가치가 된다.

 

 

이 둘 중 가장 최대 값으로 갱신한다.

 

배낭 문제 전체 코드

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

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

        int N = Integer.parseInt(br.readLine());
        int K = Integer.parseInt(br.readLine());

        int[] w = new int[N + 1], v = new int[N + 1];
        int[][] dp = new int[N + 1][K + 1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        StringTokenizer st2 = new StringTokenizer(br.readLine());

        for (int i = 1; i <= N; i++) {
            w[i] = Integer.parseInt(st.nextToken());
            v[i] = Integer.parseInt(st2.nextToken());
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= K; j++) {
                if (w[i] <= j) {
                    dp[i][j] = Math.max(dp[i - 1][j - w[i]] + v[i], dp[i - 1][j]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        System.out.println(dp[N][K]);

    }

}
728x90
반응형