[Algo] 백준 12865 평범한 배낭 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/12865

메모리 : 14820KB

시간 : 156ms

언어 : Java 11

---

코드

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

public class Main {

	public static <T> 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()); //무게
		int[][]arr=new int[N+1][2];
		for(int n=1; n<=N; n++){
			st=new StringTokenizer(br.readLine());
			arr[n][0]=Integer.parseInt(st.nextToken()); //무게
			arr[n][1]=Integer.parseInt(st.nextToken()); //가치
		}
		int []dp=new int[100001]; //물건 개수, 버틸수있는 무게
		for(int i=1; i<=N; i++){
			for(int j=K; j-arr[i][0]>=0; j--){
				//전 물건이 가졌던 값, 현재 물건이 가졌던 값(dp[현재 물건 무게를 뺀 값]+현재 물건의 값) 비교
				dp[j]=Math.max(dp[j],dp[j-arr[i][0]]+arr[i][1]);
			}
		}
		System.out.println(dp[K]);
	}
}

풀이

정말로 평범한 베낭문제!

Math.max(전 물건이 가졌던 값, 현재 물건이 가졌던 값(dp[현재 물건 무게를 뺀 값]+현재 물건의 값)) 비교