[java]평범한 배낭 - 백준12865

문제



풀이

문제 해석을 하자면,

  • 유명한 문제이며, 제한된 무게속에 제일 큰 이득을 취하는 문제이다.


풀이



코드

package ProblemSolution.DP_Detail;

import java.io.*;
import java.util.*;

/**
 * 0-1 냅색이라는 유명한 유형의 문제 @!!@!@!@
 * 풀이도 다양함!! 변형 문제도 많음!! 그리디로 푸는것도 있고 DP로도 풀고 분기한정법이나 등등 다양함
 * `max( P[i-1][w], pi + P[i-1][w-wi] )	,if wi<=w`
 * `P[i][w] = P[i-1][w]	,if wi>w`
 */
public class 평범한배낭_BOJ12865 {
    static int[][] inArr = new int[102][2];
    static int[][] P = new int[102][100002];

    static int knapsack(int n, int w) {
        // memorize dp
        if(P[n][w] > 0) return P[n][w];

        // base condition
        int wi = inArr[n][0]; // 실제 n번 물건의 무게
        if(n==1 && w>=wi) return P[n][w] = inArr[n][1];
        else if(n==1 && w<wi) return P[n][w] = 0;

        // recursion
        int pi = inArr[n][1]; // 실제 n번 물건의 이득
        if(w < wi)
            P[n][w] = knapsack(n-1, w);
        else
            P[n][w] = Math.max(knapsack(n-1,w), pi+knapsack(n-1,w-wi));
        return P[n][w];
    }

    public static void main(String[] args) throws IOException {
        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(stk.nextToken()); // 물품의 수
        int K = Integer.parseInt(stk.nextToken()); // 최대 허용 무게
        for(int i = 1 ; i<=N;i++) {
            stk = new StringTokenizer(br.readLine(), " ");
            int w = Integer.parseInt(stk.nextToken()); // 무게
            int v = Integer.parseInt(stk.nextToken()); // 가치
            inArr[i][0] = w;
            inArr[i][1] = v;
        }
        // run => Top_bottom_DP~!~!~!~!
        for(int i = 0;i<102;i++) Arrays.fill(P[i], -1);
        System.out.println(knapsack(N, K));
    }

}



느낀점

생략

댓글남기기

참고