The cooks at Roosevelt Lodge are packing the wagon for the chuck wagon cookout. They want to maximize the calories for the cookout, but the weight of the food is limited to what the horses can pull.
Before computers, the cooks would use guess-and-check to maximize the calories while meeting the weight limit. They had to repeat the exercise everytime the menu changed! Now they know that their task is an instance of the classic knapsack (0-1) problem, and they definitely need the dynamic approach. They just have to be sure to add multiple instances of the different foods to the data list. For example, there are 5 packages of steak and 8 packages of baked beans to choose from. They can only pack whole packages.
Suppose you had these foods, and the weight limit is 25 pounds:
| Food | Weight per package | Calories per package | Number of packages |
|---|---|---|---|
| Steak | 5 lb. | 10000 | 2 |
| Corn on the cob | 2 lb. | 1500 | 10 |
The maximum number of calories would be 30500.
These are the food the cooks are packaging:
| Food | Weight per package | Calories per package | Number of packages |
|---|---|---|---|
| Steak | 5 lb. | 7500 | 5 |
| Corn on the cob | 2 lb. | 1000 | 7 |
| Baked beans | 3 lb. | 2500 | 8 |
| Peach cobbler | 3 lb. | 2100 | 4 |
| Apple cider | 8 lb. | 2000 | 5 |
The weight capacity of the wagon is 75 pounds.
What is the maximum number of calories they can pack into the wagon?Copyright 2022 Robin A. Reynolds-Haertle