[SWEA] 5215. 햄버거 다이어트

knapsack 유형의 문제이다.

이 문제는 조합을 통하여 풀수 있는데 조합을 구현하는데 두가지 방법을 사용해보았다. 1번은 선택-비선택 재귀호출으로 구현하였고, 2번은 visit배열은 이용한 백트래킹 조합을 사용하여 구현하였다. 또한 두가지 방법모두 가지치기가 상당히 중요한 요소이므로 잘생각할 필요가 있다.

방법1 : 선택,비선택 재귀

package swea;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution_d3_5215_햄버거다이어트 {
    
    static int N;
    static int limit;
    static int[][] dp;
 
    static int[] grade;
    static int[] cal;
    static int answer;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        int T=Integer.parseInt(br.readLine());
        
        for(int tc=1;tc<=T;tc++) {
            st=new StringTokenizer(br.readLine());
            N=Integer.parseInt(st.nextToken());
            limit=Integer.parseInt(st.nextToken());
            
            grade=new int[N];
            cal=new int[N];
            
            for(int i=0;i<N;i++) {
                st=new StringTokenizer(br.readLine());
                grade[i]=Integer.parseInt(st.nextToken());
                cal[i]=Integer.parseInt(st.nextToken());
            }
            answer=-1;
            dfs(0,0,0);
            System.out.println("#"+tc+" "+answer);
        }
    }
    
    static void dfs(int depth, int sumGrade, int sumCal) {
        if(sumCal>limit) {
            return;
        }
        if(depth==N) {
            answer=Math.max(answer, sumGrade);
            return;
        }
        dfs(depth+1,sumGrade+grade[depth], sumCal+cal[depth]);    //선택O
        dfs(depth+1,sumGrade,sumCal);                            //선택X
    }
}
 

방법2 : 백트래킹 조합

package swea;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Solution_d3_5215_햄버거다이어트_2 {
    
    static int N;
    static int limit;
    static int[][] dp;
 
    static int[] grade;
    static int[] cal;
    
    static int[] resultGrade;
    static int[] resultCal;
    
    static boolean[] visit;
    static int answer;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        int T=Integer.parseInt(br.readLine());
        
        for(int tc=1;tc<=T;tc++) {
            st=new StringTokenizer(br.readLine());
            N=Integer.parseInt(st.nextToken());
            limit=Integer.parseInt(st.nextToken());
            
            grade=new int[N];
            cal=new int[N];
            
            resultGrade=new int[N];
            resultCal=new int[N];
            
            for(int i=0;i<N;i++) {
                st=new StringTokenizer(br.readLine());
                grade[i]=Integer.parseInt(st.nextToken());
                cal[i]=Integer.parseInt(st.nextToken());
            }
            answer=-1;
            visit=new boolean[N];
            dfs(0,0);
            System.out.println("#"+tc+" "+answer);
        }
        
    }
    
    static void dfs(int start, int depth) {
        
        int sumCal=0;
        int sumGrade=0;
        for(int i=0;i<depth;i++) {
            sumCal+=resultCal[i];
            sumGrade+=resultGrade[i];
        }
//        System.out.println(sumCal +","+ (depth));
        if(sumCal<=limit)
            answer=Math.max(answer, sumGrade);
        
        if(depth==N) {
//            System.out.println(Arrays.toString(resultCal));
            return;
        }
 
        for(int i=start;i<N;i++) {
            if(visit[i]==false) {
                visit[i]=true;
                resultCal[depth]=cal[i];
                resultGrade[depth]=grade[i];
                dfs(i,depth+1);
                visit[i]=false;
            }
        }
    }
}