[KOI 2020 1차대회 중등부] 19942번-다이어트

중요 지식

---

백트래킹 알고리즘 - 모든 재료의 조합을 살펴보면서 최선의 값을 구하기 위함

코드

---

#include <iostream>
#include <queue>

using namespace std;

struct PFCVM{
    int protein;
    int fat;
    int carb;
    int vita;
    int money = 0;
};

int N, temp[16], ansMoney = 987654321, ans[16], ansLen = 0;
bool ch[16];
PFCVM ieastFood;
vector<PFCVM> foods(16);

void input(){
    cin >> N;
    cin >> ieastFood.protein >> ieastFood.fat >> ieastFood.carb >> ieastFood.vita;

    for(int i = 1; i <= N; i++){
        cin >> foods[i].protein >> foods[i].fat >> foods[i].carb >> foods[i].vita >> foods[i].money;
    }

    return;
}

void calculate(int len){
    PFCVM tempFood = {0};

    for(int i = 1; i <= len; i++){
        tempFood.protein += foods[temp[i]].protein;
        tempFood.fat += foods[temp[i]].fat;
        tempFood.carb += foods[temp[i]].carb;
        tempFood.vita += foods[temp[i]].vita;
        tempFood.money += foods[temp[i]].money;
    }

    if(tempFood.protein >= ieastFood.protein && tempFood.fat >= ieastFood.fat && tempFood.carb >= ieastFood.carb && 
    tempFood.vita >= ieastFood.vita && tempFood.money < ansMoney){
        ansMoney = tempFood.money;
        for(int i = 1; i <= len; i++){
            ans[i] = temp[i];
        }
        ansLen = len;
    }

    return;
}

void bt(int cnt, int order){
    for(int i = cnt; i <= N; i++){
        if(!ch[i]){
            ch[i] = true;
            temp[order] = i;
            calculate(order);
            bt(temp[order], order+1);
            ch[i] = false;
        }
    }

    return;
}

int main(){
    input();
    bt(1,1);

    if(ansLen > 0){
        printf("%d\n", ansMoney);
        for(int i = 1; i <= ansLen; i++){
            printf("%d ", ans[i]);
        }
    }else{
        printf("-1");
    }
    
  
    return 0;
}

풀이

---

백트래킹 알고리즘을 활용하여 영양기준을 초과하면서 최소의 가격을 사용한 조합을 모두 탐색한다