햄버거 다이어트

1. 오케이 2. 이것이 진정한 백트래킹 3. 이것을 하는 방법 4. 조건을 잘 걸기 5. 가지치기를 잘하기 6. 어떤 조건을 걸어야, 하나의 배열만 사용해서도 가지치기 가능함 7. 백 트래킹 돌아왔을 때의 값들을 잘 저장 해두기

#include <stdio.h> #define max_burger_num 20 int taste[max_burger_num]; int calorie[max_burger_num]; int rest[max_burger_num]; int max_taste; void back_tracking(int N, int L, int index, int cal_sum, int ta_sum) { if (ta_sum + rest[index] < max_taste) // 가지치기임, 나머지 모든 것을 더했을 때에도, max_taste 보다 작으면 진행할 필요가 없음 return; if (index == N) // 5개를 선택하거나 안했을 때, { if (ta_sum > max_taste && cal_sum <= L) // 제한 칼로리 이내이고, 현재까지 sum의 과 max_taste 비교 max_taste = ta_sum; return; } else if (cal_sum > L) // cal_sum 이 L 보다 크면 return. 2번째 가지치기 return; back_tracking(N, L, index + 1, cal_sum, ta_sum); // index 만 넘어가면 그 재료는 선택하지 않음 back_tracking(N, L, index + 1, cal_sum + calorie[index], ta_sum + taste[index]); // 해당 재료를 선택함 } int main(void) { freopen("input.txt", "r", stdin); int test_no; int N; int L; int sum; scanf("%d", &test_no); for (int k = 0; k < test_no; k++) { max_taste = 0; sum = 0; scanf("%d %d", &N, &L); // 재료 종류, 칼로리 제한 for (int i = 0; i < N; i++) { scanf("%d %d", &taste[i], &calorie[i]); // 맛 점수, 칼로리 점수 저장함 sum = sum + taste[i]; // 총 맛의 점수 합 } for (int i = 0; i < N; i++) { rest[i] = sum; // 해당 선택하지 않았을 때 맛의 점수 총합 sum = sum - taste[i]; } back_tracking(N, L, 0, 0, 0); printf("#%d %d\n", k + 1, max_taste); } return 0; }