영양 요구 사항에 따라 메뉴 구성

Question

매일 7 개의 메뉴를 생성해야합니다. 메뉴는 아침, 점심, 저녁 식사 및 스낵 3 가지로 구성됩니다. 나는 fatsecret.com에서 가져온 요리법을 수백 가지 가지고있다. 각 조리법에는 칼로리, 지방, 나트륨, 섬유 등의 영양 정보가 포함되어 있습니다.

Calories: 1500 
Sodium: 200g 
Fiber: 32g 
Fat: 30g 

나는 그들을 통해 반복 및 영양 정보를 합산 한 후, 아침 식사, 점심 식사, 저녁 식사 및 간식의 가능한 모든 조합을 계산하고있어 각 매일 메뉴가 제한됩니다. 영양 요구 사항을 충족하는 7 가지 조합을 발견하자마자 중단합니다. 그러나 나는보다 효율적인 방법이 필요하다.

나쁜 메뉴를 선택하고 다른 지점을 시도 할 때마다 백업하는 트리 구조를 생각하고 있지만이 문제에 붙어 있습니다. 어떤 도움을 주셔서 감사합니다.

Answer 1

k-d tree과 같은 레시피에 대한 색인을 생성 할 수 있습니다. 이렇게하면 현재 메뉴 선택과 결합 할 수없는 레서피를 효과적으로 제거 할 수 있으며, 휴리스틱을 적용하여 유효한 조합을 찾을 가능성을 높일 수 있습니다 예 : "저녁 식사는 일일 칼로리의 50 % 이상을 차지하지 못합니다.")

Answer 2

가능한 접근 방식을 제안합니다.

샘플 조합

구현하기 쉬운입니다 첫 번째 방법은 무작위로 각 식사를위한 조리법을 선택하고 재료를 총 것입니다. 그것이 영양 한도를 만족한다면 그것을 지키십시오. 예를 들어, 수억 개의 조합을 샘플링하면 자격을 얻는 데 도움이되는 항목을 얻을 수 있습니다. 그것을 시도하는 것은 쉽다.

내가 전적으로 최적화 기법으로 DP 간주으로 동적 프로그래밍 ("DP") "영감"라고

프로그래밍 동적에서 영감 접근 방식을 사용합니다. 독자가 DP에 대해 알 필요는 없지만하는 사람에게는 "단계"가 식사가되며 각 단계의 "주"는 모든 식사에 대한 조리법에서 제공하는 영양가의 조합이 될 것입니다. 주어진 단계와 관련된 식사도 포함됩니다. 각식이 항목에 대해

, 우리가 라운드 할 수있는 가정 : 가장 가까운 20

• 칼로리를;
• 가장 가까운 5 gms의 나트륨;
• 가장 가까운 그램에 각각 섬유 및 지방.

영양 성분이 다소 다양 할 수 있다는 점을 감안할 때 이것은 무리한 것으로 보이지 않습니다.

이렇게하면 네 가지 영양소가 76 * 41 * 33 * 31 => 3,187,668 개가 허용됩니다.

0부터 5까지 여섯 개의 식사가 있습니다.

{ calories: 460, sodium: 55, fibre: 4, fat: 6 } 

하자가 키 배열 [calories, sodium, fibre, fat], 각 조합에 대해 하나 요소 k=>v와 해시 수 r[0] : 각각의 가능한 조리법을 위해, 우리는 다음과 같은 네 가지 영양 성분의 양의 해시를

20의 배수로와 0 1500 사이

• calories ;
• sodium, 0 및 200 사이에서, 5의 배수;
• fibre, 0 및 32 사이; 및
• fat, 0 및 30 사이.

주어진 키가 [calories, sodium, fibre, fat] 인 경우 해당 값은 해당 조합을 제공하는 식사 0의 요리법 세트입니다.

우리는 단순히 식사 제로에 사용할 수있는 모든 요리법을 검토합니다. 주어진 조리법이 키 k에 의해 주어진 영양 성분과 일치하는 경우, 관련 값인 r[0][k]에 이미 충분한 수의 조리법 (예 : 7)이 포함되어 있는지 확인합니다. 그렇지 않으면 값 (배열)에 해당 제조법을 추가합니다.

이제는 식사에 대해 설명 할 계산을 수행했다고 가정합니다. 0, 1, 2,..., i. r[j], 0 <= j <= i을 계산할 것입니다. r[j]은 키가 4 가지 영양가의 조합이고 그 값이 (은 매우 신중하게 다음을 읽어보십시오) 모든 식사에 대한 요리법 세트는 영양가가 높은 해시입니다. 키에 의해 주어진 값.

이제 다음 단계를 수행하여 r[j+1]을 계산합니다. 각 키 kr[j]에 대한

: 우리가 식사 j+1 각 조리법을 고려

k = [calories, sodium, fibre, fat] 

, 특징 :

[r_calories, r_sodium, r_fibre, r_fat]  

이러한 네 가지의 경우

k' = [calories+r_calories, sodium+r_sodium, fibre+r_fibre, fat+r_fat] 

을 계산 값이 관련 최대 일일 제한을 초과 함 그것, 그 특정한 열쇠를 위해 조리법은 사용될 수 없습니다. 값이 모두 한도 내에 있으면 r[j+1]의 키가됩니다. 해당 키와 관련된 값인 r[j+1][k']은 모든 음식에 대한 모든 요리법의 집합으로, j+1 식사를 포함하여 그 키에 의해 주어진 영양가가 산출됩니다. 그 값에 j+1 급식 (예 : 이전 급식 용 조리법과 함께)의 충분한 수 (예 : .. 7)의 조리법이 포함되지 않은 경우 r[j][k]에 지정된 모든 조리법과 함께 고려중인 조리법을 추가합니다. 우리는 식사 i에 대한 가능한 모든 조리법에 대해 이것을 반복합니다. 끝나면 r[i]에있는 다른 키 각각에 대해이 단계를 반복합니다 (수백만 개가있을 수 있음).

식사 j+1까지의 모든 식사에 대한 모든 요리법을 값 (배열) r[j+1][k']에 실제로 저장할 필요는 없습니다. 오히려, 우리는 단지 j+1 식사의 요리법을 저장하고 그 각각에 대해 연관된 키에 대한 포인터를 r[j]에 저장합니다.

각 r[j]에는 최대 3,187,668 개의 키가 있지만 실제로는 그 수가 매우 작습니다. 예를 들어 각 식사에 가능한 100 가지 조리법이 있다면 첫 번째 식사 이후 5 가지 식사 각각에 대해이 작업의 많아야 3187668 * 100 => 318,766,800을 수행해야합니다. 여기서 유의해야 할 중요한 점은 계산 횟수는 식사 횟수에 따라 선형 적으로 증가한다는 것입니다. 나는 계산상의 관점에서 관리가 가능할 것이라고 기대한다.

모든 값 r[5]은 최대 일일 영양가를 충족시키는 6 가지 식사의 모든 요리법 세트를 나타냅니다. 조합이 없으면 아무 것도 없습니다.

Answer 3

제한 사항이 너무 엄격하지 않은 경우 Metropolis--Hastings sampling을 사용할 수 있습니다. (그렇지 않으면 Cary의 동적 프로그램이나 정수 프로그래밍이 필요합니다.) 샘플링에 의해 도입 된 편향은 임의성을 보장하면서 실행 가능성으로 메뉴를 밀어 넣어야합니다.

무작위로 각 코스를 균등하게 선택하여 메뉴를 초기화하십시오. 메뉴가 수용 될 때까지 다음 단계를 반복하십시오. 현재 메뉴부터 무작위로 코스를 균일하게 선택하고 무작위로 균일하게 요리법을 선택하고 해당 코스에 대한 해당 요리법을 사용하여 제안 된 메뉴를 유도합니다. 메뉴의 점수을 다음과 같이 정의하십시오.

max(calories - 1500, 0)  max(sodium - 200, 0) max(32 - fiber, 0) max(fat - 30, 0) 
0.99      0.95      0.7     0.7 

(지수의 기지는 몇 가지 실험을 가치가있다. 그 과잉 열량, 나트륨, 지방 있으리라 믿고있어 나쁜 불충분 섬유 때문이다.)의 경우에만 rand (균일 유동 제안 메뉴를 유지 in [0.0, 1.0))는 제안 된 메뉴의 점수를 현재 메뉴의 점수로 나눈 값보다 작습니다.