[백준] 12865번 평범한 배낭 - Java

 

 

문제출저 

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

12865번: 평범한 배낭

 

 

문제풀이

배낭 문제, 냅색 알고리즘 문제로 조합 최적화를 찾아야 한다. 

 

허용치 k인 배낭에 무게 w의 물건들을 담아서 물건들의 가치 v가 가장 높은 경우를 구해야한다.

 

문제를 해결하기 위해 2차원 int 배열인 dp를 활용한다.

 

2차원 배열인 dp의 가로줄은 배낭의 무게, 세로줄은 아이템을 배치한다.

 

	1	2	3	4	5	6	7
1 (6,13)	0	0	0	0	0	13	13
2 (4,8)	0	0	0	8	8	13	13
3 (3,6)	0	0	6	8	8	13	14
4 (5,12)	0	0	6	8	12	13	14

 

dp[아이템의 index][무게] 

무게를 기준 dp 진행 (세로로 읽으면서 탐색) -> (1,1) (2,1) (3,1) ... (1,2) (2,2)...

무게를 허용할 수 있는 index의 무게를 만나면 담는다.

만약 아이템을 담고 남는 무게가 다음에 탐색할 아이템을 담을 수 있다면 기존의 들어온 값과 비교해 큰 값을 칸에 채운다.

 

(3, 7) 지점에서 어떻게 14에 나왔는지 주목하자.

7의 무게를 담을 수 있고 인덱스 3에는 3의 무게를 사용한다. 그러면 남은 무게는 4이다. 

그러므로 3의 윗줄에 (2,4) 지점을 확인한다.  (2,4) 지점을 값은 8 따라서 6 + 8 = 14로 나온다.

그리고 이 값은 세로줄에 13보다 크므로 대체된다. 

 

 

 

 

소스코드 

package studyGroup.july.july25;

import java.awt.print.Pageable;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

/*

조합 최적화의 문제
배당문제, 냅색 알고리즘

 */


public class 백준12865평범한배낭 {

    static int n, k;
    static int[][] board;
    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());

        board = new int[n+1][2];

        for(int i = 1; i <= n; i++)
        {
            st = new StringTokenizer(br.readLine());
            int w = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            board[i][0] = w;
            board[i][1] = v;
        }

        // 가로 : 무게수   세로 : 물건의 목차
        dp = new int[n+1][k+1];

        // 무게가 기준이 되어 물건 탐색을 시작한다.

        int answer = 0;
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= k; j++)
            {
                dp[i][j] = dp[i-1][j];

                // 여분이 있다면
                if(j - board[i][0] >= 0)
                {
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j - board[i][0]] + board[i][1]);
                }

                answer = Math.max(answer, dp[i][j]);
            }
        }

        System.out.println(answer);

    }

}