[문제]
$k$ 개의 음식 재료 중에서 몇 개를 선택하여 그 안에 포함된 4가지 영양분 [단백질, 탄수화물, 지방, 비타민] 각각의 합이 일정 수치 이상이 되도록 하고자 한다. 아래 예를 통하여 설명해보자. 우리에게 필요한 4개 성분의 최소 기준이 (100, 70, 90, 10) 이라고 가정해보자. 우리는 아래 준비된 6가지 재료 중에서 몇 개를 선택하여 각 4개의 영양분 (단백질, 지방, 탄수화물, 비타민)의 합이 최소 (100, 70, 90, 10)이 되도록 해야한다.
이 경우 모든 재료를 선택하면 해결되지만, 비용이 너무 커진다. 우리는 최소 영양분 조건을 만족하면서도 선택한 재료의 비용을 최소화해야 한다. 예를 들어 재료 {1, 3, 5}를 선택하면 영양분은 (100, 145, 130, 10)으로 조건을 만족하지만, 가격은 270이 된다. 대신 {2, 3, 4}를 선택하면 영양분 조건을 (110, 130, 90, 10)으로 만족하면서도 동시에 그 비용은 180이 되므로 앞에서 {1, 3, 5} 보다는 더 나은 선택이 된다. 여러분은 문제마다 주어진 최소 영양소 기준을 만족하는 최소 비용의 음식 재료 집합을 찾아야 한다.
| 재료 | 단백질 | 지방 | 탄수화물 | 비타민 | 가격 |
| 1 | 30 | 55 | 10 | 8 | 100 |
| 2 | 60 | 10 | 10 | 2 | 70 |
| 3 | 10 | 80 | 50 | 0 | 50 |
| 4 | 40 | 30 | 30 | 8 | 60 |
| 5 | 60 | 10 | 70 | 2 | 120 |
| 6 | 20 | 70 | 50 | 4 | 40 |
[입출력]
입력파일 food.inp 의 첫 줄에는 식재료의 개수 $k$($5 \leq k \leq 50$)가 주어진다. 다음 줄에는 우리가 만족시켜야 할 4개 영양성분의 최솟값이 4개의 정수 $mp, mf, ms, mv$ 가 주어진다. 이 값은 1이상 25000 이하의 정수이다. 이어지는 $k$개의 각 줄에는 $i$번째 식재료의 영양분과 가격이 5개의 정수 $p_i, f_i, s_i, v_i, c_i$ 가 주어진다. 이 각 값은 0 이상 500 이하의 정수이다. 여러분은 조건을 만족하는 식재료 조합 중에서 최소 비용인 재료 집합을 찾아서 그 index를 오름차순으로 한 줄에 출력해야 한다.
만일 조건을 만족하는 최소 비용의 집합이 하나 이상이면 영양분의 총합이 더 높은 조합을 선택해야 한다. 만일 이 총합까지 같다면 선택한 식재료 집합 index의 사전식 순서가 더 빠른 것을 출력한다. 즉 {2, 5, 6}이 {2, 5, 12}보다 사전식 순서로 더 빠르기 때문에 우선되어야 한다. 만일 모든 식재료를 선택해도 기본 조건을 만족하지 못할 때는 이 경우를 나타내기 위하여 숫자 zero(0)을 출력 파일의 첫 줄에 출력한다.
만일 조건을 만족하는 최소 비용의 집합이 하나 이상이면 영양분의 총합이 더 높은 조합을 선택해야 한다. 만일 이 총합까지 같다면 선택한 식재료 집합 index의 사전식 순서가 더 빠른 것을 출력한다. 즉 {2, 5, 6}이 {2, 5, 12}보다 사전식 순서로 더 빠르기 때문에 우선되어야 한다. 만일 모든 식재료를 선택해도 기본 조건을 만족하지 못할 때는 이 경우를 나타내기 위하여 숫자 zero(0)을 출력 파일의 첫 줄에 출력한다.
[풀이]O(2^50)(backtracking)
0/1냅색의 응용 문제로, 너무 자명하게 backtracking이다. 풀이는 생략한다.
가지치기도 1개만 해도 시간내 통과가 가능하며, 속도 가산점을 받기 위해 더 가지치기한 조건은 paritial 냅색을 이용한 greedy한 방법이다.
각 영양소별 가격대비 영양소의 비 중 가장 높은 비를 갖는 음식을 각각 구해놓고,
$i$상태일 때 최소 영양소 까지 남은 영양소 x 가장 가성비가 높은 음식의 1영양소당 가격 을 곱하면 $i$상태에서 최소영양소를 달성할 때 까지의 최소 가격을 구할 수 있다. 이 최소 가격이 현재 까지 구했던 answer가격보다 낮으면 pruning해주면 된다.
