[백준] 12865 평범한 배낭 [자바]

 

 

---

https://st-lab.tistory.com/141

[백준] 12865번 : 평범한 배낭 - JAVA [자바]

https://hongcoding.tistory.com/50

[백준] 12865 평범한 배낭(Python 파이썬)

https://velog.io/@uoayop/%EB%83%85%EC%83%89-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

냅색 알고리즘

https://www.acmicpc.net/board/view/60752

글 읽기 - Knapsack 알고리즘(배낭알고리즘dp) 질문ㅠㅠ

 

 

---

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

public class Main {
	static int N,K;
	static Integer[][] dp;
	static int[] W;
	static int[] V;
 	public static void main(String arg[]) 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());
 		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) {
 		if(i < 0) {
 			return 0;
 		}
 		if(dp[i][k] == null) {
 			if(W[i] > k) { //현재 무게가 w[i]를 받지 못하면
 				dp[i][k] = knapsack(i-1, k); //이전 i값을 탐색한다 (표에서 바로 위의 값)
 			}
 			else { //받을 수 있다면
 				dp[i][k] = Math.max(knapsack(i-1,k), knapsack(i-1, k-W[i]) + V[i]);
 				//이전 i값(표에서 위의 값)과 이전 i의 값(현재의 i가 포함되면 안됨) 중 현재 k의 무게에서 i 의 무게 w[i]를 뺀 무게의 가치+현재 무게의 가치 
 			}
 		}
 		return dp[i][k];
 	}
}