백준

백준 12865 평범한 배낭(Java)

Park DJ 2023. 2. 24. 17:42

https://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

 

Java 코드

 

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int max = -1;
    int n = sc.nextInt();
    int k = sc.nextInt();
    int[] w = new int[n + 1];
    int[] v = new int[n + 1];
    int[][] arr = new int[n + 1][k + 1];

    for(int i = 1; i <= n; i++) {
      w[i] = sc.nextInt();
      v[i] = sc.nextInt();
    }

    for(int i = 1; i <= n; i++) {
      for(int j = 1; j <= k; j++) {
        arr[i][j] = arr[i - 1][j];
        if(j >= w[i]) arr[i][j] = Math.max(arr[i - 1][j], arr[i - 1][j - w[i]] + v[i]);
      }
    }

    for(int i = 1; i <= n; i++) {
      for(int j = 1; j <= k; j++) max = Math.max(max, arr[i][j]);
    }

    System.out.println(max);
  }
}