acmicpc

[BAEKJOON] 12865. 평범한 배낭

코드와이 2021. 3. 23. 18:03

Knapsack

문제링크

www.acmicpc.net/problem/12865

 

12865번: 평범한 배낭

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)

www.acmicpc.net

 

package acmicpc.Gold5;

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

public class 평범한_배낭 {

	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());
		
		int[][] WV = new int[n + 1][2];
		for(int i = 1 ; i <= n ; i++) {
			st = new StringTokenizer(br.readLine());
			WV[i][0] = Integer.parseInt(st.nextToken());
			WV[i][1] = Integer.parseInt(st.nextToken());
		}
		
		int[][] arr = new int[n + 1][k + 1];
		
		for(int i = 1 ; i <= n ; i++) {
			for(int w = 1 ; w <= k ; w++) {
				int cur_w = WV[i][0];
				int cur_v = WV[i][1];
				
				if( cur_w > w ) {
					arr[i][w] = arr[i - 1][w];
				} else {
					arr[i][w] = Math.max(cur_v + arr[i-1][w - cur_w], arr[i-1][w]);
				}
			}
		}
		System.out.println(arr[n][k]);
	}
}