백준 3483 java : DP, 배낭문제

항상 최대 가치를 구하는 문제였는데 이번에는 반대로 최소가치를 구하는 문제이다. 그렇기 때문에 최대값 초기화와 Math.min 사용을 고려해야 한다.

import java.util.Arrays;
import java.util.Scanner;

public class bj3483 {
    static Scanner scanner = new Scanner(System.in);
    static int E, F; // E : 비어있는 돼지의 무게, F : 꽉 차있는 돼지의 무게
    static int [] W;// weight of coin
    static int [] P;// value of coin

    public static void main(String[] Args){
        int i, T;

        T = scanner.nextInt();
        for(i = 0; i < T; i++){
            inputData();
            System.out.println(findAnswer());
        }

        scanner.close();
    }

    public static void inputData(){
        System.out.println("\ninputData()");
        int i, N;

        E = scanner.nextInt();
        F = scanner.nextInt();
        N = scanner.nextInt();
        W = new int[N];
        P = new int[N];
        for(i = 0; i < N; i++){
            P[i] = scanner.nextInt();
            W[i] = scanner.nextInt();
        }
    }

    public static String findAnswer(){
        System.out.println("\nfindAnswer()");
        int i, j;
        int needWeight = F - E;
        int N = W.length;

        // DP 배열 초기화
        int[] DP = new int[needWeight + 1];
        Arrays.fill(DP, Integer.MAX_VALUE);
        DP[0] = 0;

        // DP 테이블 채우기
        for (i = 0; i < N; i++) {
            for (j = W[i]; j <= needWeight; j++) {
                if (DP[j - W[i]] != Integer.MAX_VALUE) {
                    DP[j] = Math.min(DP[j], DP[j - W[i]] + P[i]);
                }
            }

            System.out.print((i+1) + " : ");
            for(j = 1; j <= needWeight; j++){
                System.out.print(DP[j] + " ");
            }
            System.out.println();
        }
        System.out.println("DP[needWeight] = " + DP[needWeight]);

        // 결과 반환
        if (DP[needWeight] == Integer.MAX_VALUE) {
            return "This is impossible.";
        } else {
            return "The minimum amount of money in the piggy-bank is " + DP[needWeight] + ".";
        }
    }
}