[백준] 12865번 평범한 배낭 JAVA (자바) 풀이

 

문제 12865

 

• 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다
• 각 물건은 무게 W와 가치 V를 가지는데 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다
• 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다
• 물건들의 가치의 최댓값 구하기

 

 

 

 

[입력]

 

 :  첫 줄에 물품의 수 N(1 ≤ N ≤ 100), 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)
 :  두 번째 줄부터 N개의 줄까지 물건 무게 W(1 ≤ W ≤ 100,000), 해당 물건의 가치 V(0 ≤ V ≤ 1,000)

    ( 모든 수는 정수 )

4 7
6 13
4 8
3 6
5 12

 

 

 [출력]

 :  한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력

14

 

 

 [코드]

import java.io.*;
 
public class Main {
 
	static Integer[][] dp;
	static int[] W; // weight
	static int[] V; // value
 
	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());
		int K = Integer.parseInt(st.nextToken());
 
		W = new int[N];
		V = new int[N];
 
		dp = new Integer[N][K + 1];
 
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			W[i] = Integer.parseInt(st.nextToken());
			V[i] = Integer.parseInt(st.nextToken());
		}
 
		System.out.println(knapsack(N - 1, K));
 
	}
 
	static int knapsack(int i, int k) {
		// i가 0미만, 즉 범위 밖이 된다면
		if (i < 0)
			return 0;
		
		// 탐색하지 않은 위치라면?
		if (dp[i][k] == null) {
			
			// 현재 물건(i)을 추가로 못담는 경우 (이전 i값 탐색) 
			if(W[i] > k) {
				dp[i][k] = knapsack(i - 1, k);
			}
			// 현재 물건(i)을 담을 수 있는 경우 
			else {
				// 이전 i값과 이전 i값에 대한 k-W[i]의 값 + 현재 가치(V[i])중 큰 값을 저장  
				dp[i][k] = Math.max(knapsack(i - 1, k), knapsack(i - 1, k - W[i]) + V[i]);
			}
		}
		return dp[i][k];
	}
}

 

 [해설]
     

 :  static Integer[][] dp;  동적 프로그래밍을 위한 2차원 배열
    static int[] W;  무게
    static int[] V;  가치
 
 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
    int N = Integer.parseInt(st.nextToken());  물건 수
    int K = Integer.parseInt(st.nextToken());  배낭 최대 무게
 
    W = new int[N];  무게 배열
    V = new int[N];  가치 배열
 
    dp = new Integer[N][K + 1];  무게 제한 K를 포함
 
   for (int i = 0; i < N; i++) {  입력 차례로 저장받기
      st = new StringTokenizer(br.readLine(), " ");
      W[i] = Integer.parseInt(st.nextToken()); 
      V[i] = Integer.parseInt(st.nextToken());
    }
 
   System.out.println(knapsack(N - 1, K));  결과(최대 가치)를 출력
 
}
 
: static int knapsack(int i, int k) {       

 

       if (i < 0)  범위 밖
              return 0;  더 이상 고려할 물건이 없을 경우(인덱스가 0 미만) 0을 반환

       if (dp[i][k] == null) {  탐색하지 않은 위치

       // 현재 물건(i)의 무게가 주어진 무게(k)보다 크면, 이 물건을 담을 수 없으므로 이전 물건들만 고려
       if(W[i] > k) {  
              dp[i][k] = knapsack(i - 1, k);
       }

 

       // 현재 물건을 담을 수 있는 경우, 현재 물건을 담지 않는 경우와 담는 경우 중 최대 가치를 선택
       else {
              dp[i][k] = Math.max(knapsack(i - 1, k), knapsack(i - 1, k - W[i]) + V[i]);
       }
    }

    return dp[i][k];  계산된 최대 가치를 반환
    


 

 

이제 풀어보러 갈께요 :)

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *

 

 

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

12865번: 평범한 배낭