[알고리즘] 5215. 햄버거 다이어트

0. 문제

 

SW Expert Academy

 

민기가 좋아하는 햄버거를 먹으면서도 다이어트에 성공할 수 있도록 정해진 칼로리 이하의 조합 중에서 민기가 가장 선호하는 햄버거를 조합해주는 프로그램을 만들어보자.

 

---

1. C++

 

가. 제출

#include<iostream>
#include<algorithm>

using namespace std;

const int MAXN = 20;
int n, l, ret;
int t[MAXN], k[MAXN];

void solve(int depth, int cal, int score){
    if(depth == n){
        if(cal <= l && score > ret){
            ret = score;
        }
        return;
    }
    if(cal > l) return;
    score += t[depth];
    cal += k[depth];
    solve(depth+1, cal, score);

    score -= t[depth];
    cal -= k[depth];
    solve(depth+1, cal, score);
    return;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int T;
    cin >> T;
    for(int tc=1; tc<=T; ++tc){
        ret = 0;
        cin >> n >> l;
        for(int i=0; i<n; ++i){
            cin >> t[i] >> k[i];
        }
        solve(0, 0, 0);
        cout << "#" << tc << " " << ret << '\n';
    }
    return 0;
}

재귀함수를 사용해서 모든 조합을 생성해서 비교한다.

 

단 이미 제한 칼로리를 넘어선 경우는 생략한다.

 

---

나. 더 좋은 코드

#include <bits/stdc++.h>

using namespace std;

int n, l;
int dp[21][10001];

int main()
{
    int T;
    cin >> T;

    for (int t = 0; t < T; t++)
    {
        // l = 제한 칼로리
        cin >> n >> l;

        int score[21];
        int cal[21];

        for (int i = 1; i <= n; i++)
        {
            cin >> score[i] >> cal[i];
        }
        for (int i = 1; i <= n ; i++)
        {
            for (int j = 1; j <= l; j++)
            {
                if (cal[i] > j)
                    dp[i][j] = dp[i - 1][j];
                else
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cal[i]] + score[i]);
            }
        }
        cout << "#" << t+1 << " " << dp[n][l] << '\n';
    }

    return 0;
}

knapsack 문제라고 한다.

 

• j : 지금까지의 누적 칼로리
  
  
• if (cal[i] > j) dp[i][j] = dp[i - 1][j]; : 넣을 수 없을 경우. (추가 후 칼로리 < 추가할 칼로리)
  
  
• else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cal[i]] + score[i]);
  : 재료를 넣을 수 있는 경우. 넣는 것과 넣지 않는 것을 비교한다.
  : dp[i - 1][j - cal[i]] 재료를 넣기 전 점수 (추가 전 칼로리일 때 점수)
  
  
• dp[n][l] : n개의 재료를 l 칼로리 이하로 조합했을 때 최대 점수.

 

 

---

2. Java

import java.util.Scanner;

public class Solution
{
    static final int MAXN = 20;
    static int n, l, ret;
    static int[] t = new int[MAXN]; 
    static int[] k = new int[MAXN];

    public static void solve(int depth, int score, int cal){
        if(depth == n){
            if(cal <= l && score > ret){
                ret = score;
            }
            return;
        }
        if(cal > l) return;

        score+=t[depth];
        cal+=k[depth];
        solve(depth+1, score, cal);

        score-=t[depth];
        cal-=k[depth];
        solve(depth+1, score, cal);
        return;
    }

    public static void main(String args[]) throws Exception
    {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for(int tc=1; tc <= T; tc++){
            ret = 0;
            n = sc.nextInt();
            l = sc.nextInt();

            for(int i=0; i<n; i++){
                t[i] = sc.nextInt();
                k[i] = sc.nextInt();
            }

            solve(0,0,0);
            System.out.println("#" + tc + " " + ret);
        }
        sc.close();
    }
}

 

---

(240203 추가)

 

Java 재귀로 풀어봄.

import java.io.*;
import java.util.StringTokenizer;

public class SWEA5215 {

	static int n , l, ret;
	static int[] cals, scores; //칼로리, 점수를 저장하는 배열

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

		int T = Integer.parseInt(st.nextToken());
		for(int tc=1; tc<=T; tc++) {
			st = new StringTokenizer(br.readLine());
			n = Integer.parseInt(st.nextToken());
			l = Integer.parseInt(st.nextToken());
			ret = 0;
			
			//입력
			scores = new int[n];
			cals = new int[n];
			for(int i=0; i<n; i++) {
				st = new StringTokenizer(br.readLine());
				scores[i] = Integer.parseInt(st.nextToken());
				cals[i] = Integer.parseInt(st.nextToken());
			}
			
			solve(0, 0, 0);
			
			//조건을 만족하는 최대 점수 출력
			System.out.printf("#%d %d%n", tc, ret);
			
		}
		br.close();
	}
	
	public static void solve(int depth, int calSum, int scoreSum) {
		if(calSum > l) return; //가지치기
		if(depth == n) {
			//if(calSum > l) return; // 제한 칼로리보다 이하만 가능.
			ret=Math.max(ret, scoreSum);
			return;
		}
		
		//포함
		solve(depth+1, calSum+cals[depth], scoreSum + scores[depth]);
		//미포함
		solve(depth+1, calSum, scoreSum);
	}

}