배낭 알고리즘 knapsack problem(자바) - DP

: 배낭에 들어갈 수 있는 무게가 주어지고, 물건들의 무게와 가치가 주어진 후 총 가치가 최대가 되도록 하는 방법을 구하는 문제

 

1) 물건들을 쪼갤 수 있다고 가정하는 문제

-> 그리디 알고리즘을 사용해서 풀이

 

2)물건들을 쪼갤 수 없다고 가정하는 문제

-> DP를 이용해서 풀이

(브루트포스를 이용해서 각 물건들을 넣을 때와 안 넣을 때를 모두 고려해서 풀이할 수도 있지만 이 경우 O(2^N)의 시간복잡도를 가지기 때문에 시간초과가 발생한다.)

 

배낭 알고리즘

p[i,w]를 i개의 보석이 있고 무게의 한도가 w일 때 최적의 가치라고 하자.

 

• i번째 물건이 배낭에 들어갈 수 없다면

: i-1개의 물건이 배낭에 들어갔을 때의 최적 가치 값   -> 즉 p[i-1][w]

• i번째 물건을 배낭에 넣을 수 있다면

:  i-1개의 물건을 넣고 i번째 물건이 들어갈 공간을 남겨놓은 경우의 최적 가치 + i번째 물건의 가치  or  i-1개의 물건으로 배낭을 채웠을 때의 최적 가치   -> 즉 Math.max(p[i-1][w - item[i][0]] + item[i][1],  p[i-1][w])

 

 

import java.util.Scanner;

public class Knapsack_Problem {
    static int n,k;
    static int[][] items;
    static int max;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextInt();
        items = new int[n+1][2];
        for (int i = 1; i <= n; i++) {
            items[i][0] = sc.nextInt();
            items[i][1] = sc.nextInt();
        }
        max = 0;

        int[][] dp = new int[n+1][k+1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k; j++) {
                if (items[i][0] > j) {   //현재 물건의 무게가 배낭에 들어갈 수 있는 무게보다 클 때
                    dp[i][j] = dp[i-1][j];
                }
                else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-items[i][0]] + items[i][1]);
                }
            }
        }
    }
}

 

 

참고

[Java]배낭 문제(Knapsack Problem) :: TH (tistory.com)

[Java]배낭 문제(Knapsack Problem)

Dynamic Programming: 배낭 채우기 문제 (Knapsack Problem) (tistory.com)

Dynamic Programming: 배낭 채우기 문제 (Knapsack Problem)