So in front of me lies different items. To buy each item you will need a certain amount of multiple things. For example, to buy a lamp, you will need to pay 3 apples, 4 oranges and 17 bananas. Each item has it's monetary value, and some items can only be unlocked after another item is bought.

To rephrase:

There are n items each with a value of kv.

For each item k, it will cost you a different amount of w, x, y, z.

For some item ki, another item kj needs to be bought for ki to be buyable.

Given a certain amount of w, x, y and z, maximise the total value bought, identifying which items to buy.

I'm figuring out what algorithm I can probably look into. If you take away the item unlocking part then it looks like a knapsack with multiple weights on each item. What is my best bet on this?

  • $\begingroup$ Yes, in the simplest case ($x=y=z=0$, no unlocking), it's a knapsack problem, so you won't be able to solve it efficiently without additional conditions (e.g. $w,x,y,z$ are small integers). $\endgroup$ – Dmitry Jul 31 at 23:57

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.