BOJ) 평범한 배낭

평범한 배낭

12865번: 평범한 배낭

풀이

 

짐의 개수 n, 버틸 수 있는 무게 k, n개 만큼의 짐의 정보 (무게 w,  가치 v)가 주어진다.

최대한 k에 맞추어, 최대 가치(max v)를 찾는 문제다.

dp의 크기를 최대 가치 k까지 입력받을 수 있도록, k+1만큼 생성해준다.

짐의 정보를 순회하면서 w와 v를 가져온다.

그리고 k 부터 w까지 무게를 줄여나가면서, 현재 무게 ( i )의 dp값(가치) 과 dp[i-w] (해당 짐을 넣기 전 가치) + v (넣으려는 짐의 가치) 값중 더 큰 값을 저장하며 k가 취할 수 있는 최대값을 찾아나간다.

 

 

코드

 

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

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()), k = Integer.parseInt(st.nextToken());
        int[][] baggageArr = new int[n][2];

        for(int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<2; j++)  baggageArr[i][j] = Integer.parseInt(st.nextToken());
        }
        br.close();
        solution(k,baggageArr);
    }

    private static void solution(int k, int[][] baggageArr) {
        int[] dp = new int[k+1];
        for(int[] baggage : baggageArr) {
            int w = baggage[0], v = baggage[1];
            for(int i =k; i>=w; i--)    dp[i] = Math.max(dp[i], dp[i-w] +v);
        }
        System.out.println(dp[k]);
    }
}