I am a computer science student that is struggling with a problem of mathematical nature. Thus far I have only studied calculus, discrete mathematics and linear algebra, but cannot figure out how to approach this problem. I tried Stack Exchange, but due to the mathematical nature they suggested me to ask here, so here goes:
I am trying to create shopping lists from a collection of products, where the returned shopping list should be optimized for cost as well as to meet another condition.
For example, let's say that I want to create shopping lists based on the energy content of the products. When the user enters a total sum, the returned shopping list should try to max out the kcal content while keeping the total sum at or around the sum specified by the user.
I've gotten so far as to create the collection of products, and all products are stored as objects with fields holding nutritional values and price etc. The kcal-value is also stored as a member variable in each product's object.
At first I considered looping through all combinations of products, sort out those that are way out of the price interval, and then return the one with the highest kcal content. But as the numbers of products available increases this soon becomes a non-viable option I think.
I now wonder if there is any algorithm to solve this problem, if not, is there any way to easily implement this?
I've understood that this is a problem of linear type, (discrete?, diophantine?), but that's about all.
This is close to a linear programming problem, but not quite there since you probably can't suggest the user to buy 0.843433 cans of crushed tomatoes or whatever.
It looks like a binary knapsack problem: minimizing a weighted sum subject to a single linear constraint, along with integrality requirements. The bad news is that this is an NP problem. The good news is that it's one of the easiest NP problems to solve, close to trivial. You will have no problems finding algorithms to implement.
The model would be
$$\max \sum k_i x_i \\ @ \sum c_i x_i \leq C$$
where $x_i$ is the number of products of type $i$ to buy, $k_i$ is the calory content of product $i$, $c_i$ is the cost of $i$ and $C$ is the users total budget.