DP - Knapsack (배낭문제)

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

12865번: 평범한 배낭

 

 

🕹️ Knapsack 알고리즘 과정 

DP 문제 중 하나로, 배낭의 크기 k와 n개의 물건의 무게(w)와 가치(v)가 주어졌을 때, 가방에 물건을 k에 넘지 않도록 넣고 최대 가치의 합을 구하는 문제이다. 

 

ex) 배낭의 크기는 k이고, 5개의 물건의 무게와 가치가 다음과 같이 주어졌을 때, 최대 가치의 합을 구하기

• 물건 1 : w = 3, v = 8
• 물건 2 : w = 1, v = 5
• 물건 3  : w = 2, v = 7
• 물건 4 : w = 2,  v = 2
• 물건 5 : w = 2, v = 6

• 물건 1만 배낭에 넣었을 경우

• 물건 2도 배낭에 넣었을 경우

• 물건 5까지 모두 넣었을 경우 

 

 

점화식 
➡️ 물건을 담을 수 없는 경우 (j<w)
👉 dp[i][j] = dp[i-1][j] 

➡️ 물건을 담을 수 있는 경우 (j>=w ➔ else)
👉 dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);

 

 

 

 👩‍💻 Knapsack 구현 코드

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));
    StringTokenizer st = new StringTokenizer(br.readLine());
    
    int n = Integer.parseInt(st.nextToken());  
    int k = Integer.parseInt(st.nextToken());  
    
    int[][] dp = new int[n+1][k+1];
    int[] w = new int[n+1];  
    int[] v = new int[n+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] = Math.max(dp[i-1][j-w[i]]+v[i], dp[i-1][j]);
        } else {
          dp[i][j] = dp[i-1][j];
        }
      }
    }
    System.out.print(dp[n][k]);
  }
}