배낭 문제 해결

새로운 함수 KnapsackSolve는 배낭 문제 등의 조합 최적화 문제 해결을 위한 쉽고 사용 조작이 간편한 방법을 제공합니다. 배낭 문제는 이차원 절단 문제와 자본 예산 등의 다양한 분야에서 나타나며, 암호화 시스템 구축에 사용할 수 있습니다.

다음의 쇼핑 목록에는 각각의 과일이 칼로리, 평균 가격, 최대 개수와 함께 지정되어 있습니다.

In[1]:=

fruits = <| Entity["FoodType", "Apple"] -> {Quantity[91, "LargeCalories"], Quantity[2.36, "Euros"], 3}, Entity["FoodType", "Orange"] -> {Quantity[71, "LargeCalories"], Quantity[2.12, "Euros"], 3}, Entity["FoodType", "Banana"] -> {Quantity[105, "LargeCalories"], Quantity[1.89, "Euros"], 5}, Entity["FoodType", "Kiwi"] -> {Quantity[103, "LargeCalories"], Quantity[3.77, "Euros"], 10}, Entity["FoodType", "Pear"] -> {Quantity[96, "LargeCalories"], Quantity[2.87, "Euros"], 5}|>;

주어진 금액으로 칼로리가 최대가 되도록 각각의 과일의 개수를 결정합니다.

In[2]:=

counts = KnapsackSolve[fruits, Quantity[25, "Euros"]]

Out[2]=

다음은 각각의 과일에서 칼로리의 분포 및 그 합계입니다.

In[3]:=

fruits[[All, 1]] counts

Out[3]=

In[4]:=

fruits[[All, 1]] counts; Total[%]

Out[4]=

아래는 각각의 과일의 가격 및 총 가격입니다.

In[5]:=

fruits[[All, 2]] counts

Out[5]=

In[6]:=

fruits[[All, 2]] counts; Total[%]

Out[6]=