2
$\begingroup$

I think it will be best to explain the problem first and then explain what I am thinking:

I have a dataset similar to the following:

fruit,calories,cost
apple,100,1
apple,200,1.5
apple,150,2
pear,300,3
pear,100,.5
pear,250,2
orange,100,1
orange,120,1
orange,400,2

And I am trying to maximize my calories while keeping my cost within a certain range. At this point it is just a knapsack problem, but what if I have to have 1 apple, 1 pear, and 2 oranges, or some other arbitrary set of fruit numbers?

I can't really wrap my head around how this should work, given the extra constraint. I've thought about trying to merge my cost and calories into 1 metric somehow, but I am pretty sure that can't work since it loses.

My most recent thought is potentially keeping track of fruit count in a list, and if the proper amount of fruit has been reached it will skip to the next fruit. I am thinking about this in a similar way to a knapsack with 3 constraints, weight, value, and size, but the size is just fruit count essentially.

Hoping someone on here can tell me if I am heading in the right direction or if there is an algorithm that does this that I can look into.

Thank you!

$\endgroup$
  • $\begingroup$ Isn't it possible that you distribute what is needed first and then after you've done that, the problem reduces to your standard Knapsack problem? Or am I missing something? $\endgroup$ – Gokul Jul 18 at 13:39
  • $\begingroup$ Maybe, I am not sure what you mean though, can you explain a bit more? $\endgroup$ – Jacob D Jul 18 at 23:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.