[BOJ/JAVA] 12865(평범한 배낭)

1. Link

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

2. 풀이 과정

대표적으로 유명한 Knapsack Problem
DP 또는 BackTracking으로 푸는 것이 자명한 이유로, DP 풀이를 진행해봤습니다.
-> 분할 가능한 배낭 문제라면 그리디 알고리즘으로도 해석 가능하다

• Knapsack Problem이라는 조합 최적화 문제의 일종입니다. 가치의 합이 최대가 되며 무게를 넘지 않는 최적 부분집합을 찾는 문제이므로 O(N * K)의 시간복잡도로 해결 가능합니다.

3. 정답 코드

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    static int n, k, answer = 0;
    static int[][] dp;
    static Point[] item;

    static void input() throws IOException {
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        item = new Point[n + 1];
        for (int i = 1; i <= n; ++i) {
            st = new StringTokenizer(br.readLine());
            int w = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            item[i] = new Point(w, v);
        }
        dp = new int[n + 1][k + 1];
    }

    static void solution() {
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= k; ++j) {
            	//i번째 아이템의 무게를 배낭이 안고 갈 수 있는 경우와 
                //담지 않고도 더 큰 값을 가지는 직전 동일 무게인 경우를 비교하여 최대값을 가진다.
                if(j >= item[i].x){
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - item[i].x] + item[i].y);
                }
                //무게가 over될 경우에는 직전 동일 무게의 값을 복사해온다.
                else{
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        System.out.println(dp[n][k]);
    }

    public static void main(String[] args) throws IOException {
        input();
        solution();
    }
}

4. 추천 음악

Opening - Lucy
Link: https://www.youtube.com/watch?v=dqnYdGmspc4

요즘 밖에 나갈 때 기분 좋게 들는 플리가 있는데 이 노래가 유독 좋아서 추천해봐요~!!