import java.util.*;
import java.io.*;
class Solution {
static final int SCORE = 0;
static final int CALORIE = 1;
static int N;
static int L;
static int max;
static int[][] arr;
public static void main(String[] args) throws Exception {
//System.setIn(new FileInputStream("input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
for (int t = 0; t < T; t++) {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken()); // 재료 개수
L = Integer.parseInt(st.nextToken()); // 제한 칼로리
max = 0;
arr = new int[N][2];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
arr[i][SCORE] = Integer.parseInt(st.nextToken());
arr[i][CALORIE] = Integer.parseInt(st.nextToken());
}
dfs(0, 0, 0);
sb.append(String.format("#%d %d\n", t + 1, max));
}
System.out.println(sb);
}
static void dfs(int count, int score, int calorie) {
if (count >= N) {
if (calorie <= L) {
max = Math.max(score, max);
}
return;
}
// 선택하는 경우
dfs(count + 1, score + arr[count][SCORE], calorie + arr[count][CALORIE]);
// 선택하지 않은 경우
dfs(count + 1, score, calorie);
}
}
import java.util.*;
import java.io.*;
class Solution {
static final int SCORE = 0;
static final int CALORIE = 1;
public static void main(String[] args) throws Exception {
//System.setIn(new FileInputStream("input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
for (int t = 0; t < T; t++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); // 재료 개수
int L = Integer.parseInt(st.nextToken()); // 제한 칼로리
int[][] arr = new int[N + 1][2];
for (int i = 1; i < N + 1; i++) {
st = new StringTokenizer(br.readLine());
arr[i][SCORE] = Integer.parseInt(st.nextToken());
arr[i][CALORIE] = Integer.parseInt(st.nextToken());
}
int[][] dp = new int[N + 1][L + 1];
for (int i = 1; i < N + 1; i++) {
for (int j = 1; j < L + 1; j++) {
if (arr[i][CALORIE] > j) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = Math.max(dp[i - 1][j], arr[i][SCORE] + dp[i - 1][j - arr[i][CALORIE]]);
}
}
}
sb.append(String.format("#%d %d\n", t + 1, dp[N][L]));
}
System.out.println(sb);
}
}
knapsack
문제이다.점수
와 칼로리
가 주어졌을 때 칼로리
가 L
이하인 경우에서 가장 높은 점수
를 구하는 문제이다.dp
와 dfs
모두 현재 시점에서 선택할 것이냐, 말것이냐를 따지는 문제이다.N
개라고 했을 때 arr[N][2]
배열에 점수와 칼로리를 저장한다.dfs
메서드를 만든다. count
만 갱신하고 나머지 파라미터는 갱신하지 않는다.0-1 배낭문제
의 전형적인 풀이를 사용하면 된다.
dp[재료 개수][칼로리 제한]
형태로 dp
테이블을 준비한다.
이중 for문을 순회하며 dp테이블에 현재 칼로리(j)
에서의 최대 점수를 채워 나간다.
만약 현재 칼로리(j)
보다 재료의 칼로리가 더 크다면 선택할 수 없다. 따라서 이전의 선택dp[i-1][j]
로 테이블을 갱신한다.
만약 재료를 선택할 수 있다면, 재료를 넣는 경우와 넣지 않는 경우에 대해서 더 큰값을 넣어야 한다. 그에 대한 점화식은 아래와 같다.
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-arr[i][CALORIE])+arr[i][SCORE]
점화식이 어렵긴하지만, 동적 테이블을 간략하게 그려보면 현재 칼로리(j)상황에서 새로운 값을 넣냐, 이전 값을 선택하냐에 대한 상황을 유추할 수 있다.
dfs
의 경우는 코드가 직관적이기 때문에 간단히 이해할 수 있으나, dp
는 선택하는 경우를 구하기 매우 까다롭다.knapsack
문제라는 것을 알 수 있었고 바로 찾아봐서 문제를 해결했다.dp
가 매번 문제를 풀 때마다 점화식이 헷갈려서 어려웠었는데, 표를 그리면서 생각해보니 이전거를 선택하는 경우와 현재꺼를 더하는 경우에 대한 이해가 직관적으로 됐었다.