# Value Maximisation Algorithm with multiple costs

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?

• 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). – Dmitry Jul 31 at 23:57