[Java] SWEA 3282 Knapsack

3282 Knapsack 문제 링크

#1

package week01;

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

public class SWEA_3282 {
    static int[][] bag;
    static int N;
    static int M;
    static int answer;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());
        for(int t=1; t<=T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());

            bag = new int[N][2];
            boolean[] visited = new boolean[N];
            for(int i=0; i<N; i++) {
                st = new StringTokenizer(br.readLine());
                bag[i][0] = Integer.parseInt(st.nextToken());
                bag[i][1] = Integer.parseInt(st.nextToken());
            }

            StringBuilder sb = new StringBuilder();
            sb.append("#").append(t).append(" ").append(dfs(visited, 0, 0, 0));
            System.out.println(sb);
        }
    }

    static int dfs(boolean[] visited, int V, int nowC, int level) {
        if(V>=M || level>=N) return nowC;
        

    if(!visited[level] && V+bag[level][0]<=M) {
        visited[level] = true;
        nowC += bag[level][1];
        V += bag[level][0]; 
        answer = Math.max(dfs(visited, V, nowC, level+1), answer);
        nowC -= bag[level][1];
        V -= bag[level][0];
        visited[level] = false;
    }
    answer = Math.max(dfs(visited, V, nowC, level+1), answer);
    
    return answer;
}
}

• 백트래킹으로 풀려고 시도해봤는데 시간초과남
• 백크래킹이 시간초과면 이제 답이 없음.. DP임..

#2

방법을 알긴 했는데
다음에 다시 시도해야지