식재료 N개 중에서 몇 개를 선택해서 이들의 영양분 (단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되도록 해야 한다.

아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택하여 이들의 영양분(단백질, 지방, 탄수화물, 비타민)의 각각 합이 최소 (100, 70, 90, 10)가 되도록 하는 경우를 생각해보자.

이 경우 모든 재료를 선택하면 쉽게 해결되지만 우리는 조건을 만족시키면서도 비용이 최소가 되는 합리적인 선택을 해야 한다.

예를 들어 식재료 {1, 3, 5}를 선택하면 영양분은 (100, 145, 130, 10)으로 조건을 만족하지만 가격은 270이 된다.

대신 {2, 3, 4}를 선택하면 영양분의 합은 (110, 130, 90, 10), 비용은 180이 되므로 앞서의 {1, 3, 5} 보다는 더 나은 선택이 된다.

여러분은 주어진 식재료 표에서 제시된 최저 영양소 기준을 만족하는 최소 비용의 식재료 집합을 찾아야 한다.

다이어트 timer 2s memory 512MB

다이어트 2s 512MB