728x90
단계별로 풀어보기 동적계획법1의 마지막 단계 (14단계) 12865문제
그 유명한 0/1 Knapsack 문제이다.
이번학기 알고리즘 수업 시간에 아주 많이 다룬 문제라서 쉽게 풀 수 있었다.
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int maxWeight = in.nextInt();
int[] weight = new int[n];
int[] value = new int[n];
for (int i = 0; i < 2 * n; i++) {
if(i % 2 == 0) weight[i / 2] = in.nextInt();
else value[i / 2] = in.nextInt();
}
int[][] arr = new int[n + 1][maxWeight + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= maxWeight; j++) {
if (i == 0 || j == 0) {
arr[i][j] = 0;
} else if (weight[i - 1] <= j) {
arr[i][j] = Integer.max(arr[i - 1][j], value[i - 1] + arr[i - 1][j - weight[i - 1]]);
}
else {
arr[i][j] = arr[i - 1][j];
}
}
}
System.out.println(arr[n][maxWeight]);
}
}
728x90
'알고리즘 문제' 카테고리의 다른 글
[백준] 15649번 N과 M (1) (0) | 2020.01.06 |
---|---|
[백준] 14502번 연구소 (0) | 2020.01.05 |
[백준] 9251번 LCS (Longest Common Sequence) (0) | 2020.01.04 |
[백준] 1904번 01타일 (0) | 2020.01.04 |
[백준] 1003번 피보나치 함수 (0) | 2020.01.04 |