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

SWEA 햄버거 다이어트 (D 3)

package test;

import java.util.*;
import java.io.FileInputStream;

public class Swea5215 {
	static int[] score;
	static int[] calory;
	static int n;
	static int max;
	public static void main(String args[]) throws Exception
	{
		//System.setIn(new FileInputStream("res/input.txt"));

		/*
		   표준입력 System.in 으로부터 스캐너를 만들어 데이터를 읽어옵니다.
		 */
		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();
		/*
		   여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
		*/

		for(int test_case = 1; test_case <= T; test_case++)
		{
			n = sc.nextInt();
			int cal = sc.nextInt(); // 최대 칼로리
			score = new int[n];
			calory = new int[n];
			max = 0;
			for(int i = 0; i < n; i++) {
				score[i] = sc.nextInt();
				calory[i] = sc.nextInt();
			}
			run(0, 0, 0, cal);
			System.out.println("#" + test_case + " " + max);
		}
	}
	
	static void run(int level, int sum, int scores, int cal) {
		if(sum > cal) {
			return;
		}
		
		if(level == n) {
			if(sum <= cal) {
				max = Math.max(scores, max);
			}
			return;
		}
		
		run(level + 1, sum + calory[level], scores + score[level], cal);
		run(level + 1, sum, scores, cal);
	}
}

 

KnapSack (배낭) 문제

n개의 배낭과 물건이 있을 때 배낭의 최대 용량을 초과하지 않고 배당에 담을 수 있는 물건의 최대 가치 합을 구하는 문제

 

재귀 함수로 풀 수도 있다.

👉 나(level)을 포함하며 탐색하거나 포함하지 않고 탐색하는 방법

run(level + 1, sum + calory[level], scores + score[level], cal);
run(level + 1, sum, scores, cal);