I've got a real-world issue that I'm trying to come up with a dynamic programming algorithm to solve. It's similar in appearance to the knapsack problem, but it has more constraints, which has got me stumped. A simplified version of the problem:
Suppose I need to fill a basket with an arbitrary number of items c. The items have four properties: w, x, y, and z, each of which has a positive or negative number, with z being equal to the mean of the other three properties. My goal is to pick items such that the average z of my c items is at a maximum, but also
min(avg(w), avg(x), avg(y)) > d
for some arbitrary value d.
So, for example, c items each with w, x, and y (respectively) of (1000, 1000, -1), would have a very high average z (666.3), but would fail the second constraint if we set d >= 0, as the average y is -1.
The input would be the set of items from which to choose and the values of c and d, and the output would be a list of the c items I need to select to make the optimum full basket. Note that an item can only be selected once (no duplicates).
As I mentioned, I can see an obvious similarity to the knapsack problem, but I'm having trouble wrapping my mind around how to modify its basic structure to account for these different constraints. Or perhaps I am barking up the wrong tree trying to use the knapsack problem as a model?
Any input/pseudocode would be appreciated!