[backtracking] eating_puzzle

프로그램 명: eating_puzzle

제한시간: 1 초

암소 베시는 다이어트를 하고 있다. 하루 칼로리양 C 를 정해 이를 초과해서 먹지 않을려고 한다. 그런데 , 농부 존은 맛있는 것이 가득 든 B 개의 바구니를 베시에게 주어 식욕을 자극하고 있다. 각 바구니에는 일정한 양의 칼로리를 가지고 있다.

당신의 일은 주어지는 C 를 초과하지 않는 상태에서 가장 이상적인 조합을 찾도록 베시를 도와 주는 것이다.

예를 들어, 한도가 40 칼로리이고 6 개의 바구니에 각각 7 , 13 , 17 , 19 ,29 , 31 의 칼로리를 가진 바구니가 주어진다면

• 7 + 31 = 38 ,
• 7 + 13 + 19 = 39 ,
• ...

이 중 39 가 먹을 수 있는 최대 칼로리 양이다.

입력

• 첫 번째 라인은 2 개의 정수 C (10 ≤ C ≤ 35,000) , B (1 ≤ B ≤ 21) 가 주어진다.
• 다음 라인은 B 개의 정수가 주어진다. 각 정수는 1 ,2 ,3 .. 바구니의 칼로리이다.

출력

한도를 초과하지 않고 먹을 수 있는 최대 칼로리 양이다.

입출력 예

입력

40 6
7 13 17 19 29 31

출력

39

출처: USACO December 06 Bronze

#include <stdio.h>
 
#define MAX 30
 
int Food[MAX];
int Visit[MAX];
int Cal;
int Num;
int Max = 0;
 
void input()
{
    int i;
    scanf("%d %d", &Cal, &Num);
    for(i=0; i<Num; i++)
        scanf("%d", &Food[i]);
}
 
void back(int sum)
{
    int i;
    if(sum > Cal)
        return;
    if(sum <= Cal)
    {
        if(Max < sum)
            Max = sum;
    }
 
    for(i=0; i<Num; i++)
    {
        if(Visit[i] == 0)
        {
            Visit[i] = 1;
            back(Food[i]+sum);
            Visit[i] = 0;
        }
    }
 
}
 
int main(void)
{
    input();
    back(0);
    printf("%d\n", Max);
 
    return 0;
}