배낭문제

일명 냅색 알고리즘은 크게 두 가지 문제로 분류 될 수 있다.

1. 짐을 쪼갤 수 있는 배낭문제 (Fraction Knapsack Problem)
   • 탐욕 알고리즘 (Greedy) 사용
2. 짐을 쪼갤 수 없는 배낭문제 (0/1 Knapsack Problem)
   • DP 법 사용 (다이나믹 프로그래밍)

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

public class Main2 {
    static int N, K;
    static int[] W;
    static int[] V;
    static int[][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        W = new int [N + 1];
        V = new int [N + 1];
        dp = new int[N+1][K+1];

        for(int i = 1; i <= N; i++){
            st = new StringTokenizer(br.readLine());
            W[i] = Integer.parseInt(st.nextToken());
            V[i] = Integer.parseInt(st.nextToken());
        }
        
        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= K; j++){
                if(W[i] > j){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j - W[i]] + V[i]);
                }
            }
        }
        System.out.print(dp[N][K]);
    }
}

1. 배열의 크기를 N+1로 두는 이유

👉 0번 인덱스를 사용하기 위해:
예를 들어, dp[0][...]는 어떤 물건도 고려하지 않았을 때의 상태를 의미.
물건의 개수가 N개일 때, 인덱스는 1부터 N까지 사용하므로, 0번 인덱스를 포함해서 N+1개의 공간이 필요!

2. dp 구조이해

dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - W[i]] + V[i]);

• dp[i][w]는 i번째 물건까지 고려했을 때 배낭의 무게가 w일 때의 최대 가치를 의미
• 이전 값 vs 무게 계산된 이전값 + 현재 넣으려는 가치
• 최종적으로 dp[N][K] 에 가장 큰 가치가 들어가게 됨

배열 채우는 순서 비교!

        for (int j = 1; j <= K; j++) { // 무게
            for (int i = 1; i <= N; i++) { // item
                if (W[i] > j) {
                    dp[i][j] = dp[i - 1][j];
                }
                else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - W[i]] + V[i]);
                }
            }
        }

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

무게 기준 반복 (첫 번째 코드)의 경우, 무게가 커질수록 DP 테이블을 채우는 데 더 많은 시간이 걸릴 수 있다!!

예시:

• 아이템 개수 (N): 5
• 최대 무게 (K): 100

아이템 정보:

아이템	무게 (W)	가치 (V)
1	10	60
2	20	100
3	30	120
4	40	140
5	50	160

첫 번째 코드 (무게 기준 반복):

        for (int j = 1; j <= K; j++) { // 무게
            for (int i = 1; i <= N; i++) { // item
                // ...
            }
        }

• 이 코드는 무게 j를 1부터 100까지 순차적으로 증가시키면서 각 무게에 대해 아이템을 하나씩 고려합니다.
• 무게가 작은 경우 (예: j = 10)에는 빠르게 DP 테이블을 채울 수 있습니다.
• 하지만 무게가 커질수록 (예: j = 90) 모든 아이템에 대해 dp[i-1][j-W[i]] + V[i] 를 계산해야 하기 때문에 시간이 오래 걸립니다.
• 특히, 무게가 큰 아이템 (예: W[5] = 50)을 고려할 때, j - W[i] 가 음수가 되는 경우도 발생합니다. 이 경우 dp[i-1][j-W[i]] 는 의미가 없기 때문에 불필요한 계산을 수행하게 됩니다.

두 번째 코드 (아이템 기준 반복):

        for (int i = 1; i <= N; i++) { // item
            for (int j = 1; j <= K; j++) { // 무게
                // ...
            }
        }

• 이 코드는 아이템 i를 하나씩 고려하면서 각 아이템에 대해 가능한 모든 무게를 검사합니다.
• 무게가 커지더라도 아이템은 5개만 있기 때문에, 아이템 기준 반복은 항상 일정한 횟수만큼 수행됩니다.
• 즉, 무게가 커져도 시간 복잡도가 증가하지 않습니다.

결론:

• 무게가 커질수록 첫 번째 코드 (무게 기준 반복)는 불필요한 계산을 수행할 가능성이 높아지며, 시간 복잡도가 증가할 수 있습니다.
• 두 번째 코드 (아이템 기준 반복)는 무게에 상관없이 일정한 시간 복잡도를 유지하기 때문에 무게가 큰 경우 더 효율적입니다.

추가 설명:

• 실제로 무게가 매우 크거나 아이템 개수가 많은 경우, 첫 번째 코드의 시간 복잡도는 매우 크게 증가할 수 있습니다.
• 반면, 두 번째 코드는 아이템 개수에만 영향을 받기 때문에 무게가 커져도 시간 복잡도가 크게 증가하지 않습니다.

따라서, 무게가 큰 경우에는 아이템 기준 반복 (두 번째 코드)가 더 효율적인 선택입니다.

참고 : https://st-lab.tistory.com/141