Knapsack With 4 Constraints

Question

I am trying to figure out the logic for a knapsack with four constraints. I want to make a program where you input the calories, fat, carbs, and protein you want to consume in a meal and it looks through a list of possible foods for the closest combination of foods that would meet the input criteria.

Example

I have these items

• 4oz beef (231 calories, 15g fat, 0g carbs, 22g protein)
• 1/2 cup oatmeal (260 calories, 2g fat, 58g carbs, 10g protein)
• 1/2 cup black beans (120 calories, .5g fat, 23g carbs, 7g protein)
• 1 banana (105 calories, 0g fat, 27g carbs, 1g protein)
• 1/2 cup cottage cheese (110 calories, 5g fat, 6g carbs, 11g protein)
• 1/2 cup whole wheat pasta (200 calories, 1g fat, 40g carbs, 8g protein)

and my goal is to consume 745 calories, <= 20g fat, <=80g carbs, >= 40g protein

I've seen a lot of implementations of the knapsack problem, but I've never seen it with 4 constraints. My question is if it is do-able. Can you lead me to the right algorithms for my program? Thank you.

Answer 1

This is basic Linear Programming. You should look at a solver for these types of problems. In the Microsoft world - the Solver Foundation will solve this. You can also play with the Excel solver to see it done interactively.

Lot's of open source solutions too. If you prefer to do the code yourself- and need a general solution, use array math - you will be solving a system of equations of inequalities. That way you can handle N constraints and Y variables.