1
$\begingroup$

I'm developing an application to calculate the optimal build order for a strategy game. While doing so, I stumbled over an interesting problem which might be applicable to other cases as well. I will give my specific problem below as example, but I wan't to ask for an general answer. Therefore, i will give formulate the general problem:

We have a set of items with elements $I$. Each item specifies a set of $p$ properties which are positive real numbers or zero. Say the properties are numbered and $I(x)$ is the value of the $x$th property. There is a function $P$ which specifies the price of an item $P(I)$. We have a list of items $B=\{I_1,I_2,...,I_k\}$ which contains all items we have bought. The total price of $B$ is $P(B)=\sum\limits_{i=1}^k P(I_i)$ and the value of $B$ is $V(B)=\prod\limits_{j=1}^p(c_j+\sum\limits_{i=1}^k I_k(j))$ where $c_j$ is a positiv real number.

Question 1: For a given set of items and a given maximum price, find a list $B$ of items, so that $P(B_1)<\hat{P}$ and $V(B)$ is maximal.

The real problem is about an order to get the items in. The difficulty is that you can't exchange items as you wish. Only certain items of a lower price can be combined to more expensive items. In other words: You can exchange cheap items you already have for expensive items. Say we have a relation $C$ which matches the cheap items with the expensive ones you can exchange them for. This might be something like $C=\{(I_1,I_2,I_3),(I_3,I_4)\}$ for "item one and two can be exchange for item three and item three can be exchange for item four". It is important to say that $P(I_3)\neq P(I_1)+P(I_2)$. The option to combine items only allows to remove items from your old list, when you add the more expensive one to your new list. They do not change the price of your items (clarification in the example).

Question 2: For a given list $B_0$ and a given maximum price $\hat{P}>P(B_0)$, find a list $B_1$ of items so that $B_1$ contains all items of $B_0$ or there combinations, so that $P(B_1)<\hat{P}$ and $V(B_1)$ is maximal.

Question 3: For a given series of maximum prices $(\hat{P}_n)_{n\in\mathbb{N}}$ with $\hat{P}_n<\hat{P}_{n+1}$, find a series of lists $(B_n)_{n\in\mathbb{N}}$ with $P(B_n)<\hat{P}_n$ and the combination criteria from the question above, so that $\sum\limits_{n=0}^N V(B_n)$ is maximal for a given $N$.

Example: The example is taken from the popular game League of Legends. We have the following items:

Item        | AS | AD | CS | CB | Price
Dagger      | .12|  0 |  0 |  0 |  300
Gloves      |  0 |  0 | .10|  0 |  400
Bow         | .25| 15 |  0 |  0 | 1000
Zeal        | .15|  0 | .20|  0 | 1300
Hurricane   | .40| 15 | .30|  0 | 2600
Sword       |  0 | 40 |  0 |  0 | 1300
Pickaxe     |  0 | 25 |  0 |  0 |  875
Cloak       |  0 |  0 | .20|  0 |  800
Edge        |  0 | 70 | .20| .50| 3600

The cobinations are:

Dagger + Dagger -> Bow
Dagger + Gloves -> Zeal
Zeal + Bow -> Hurricane
Sword + Pickaxe + Cloak -> Edge

Value function (a variation of the DPS formula): $V=(0.5+AS)*(50+AD)*(1+CS)*(1+CB)$ (in other words: the constants $c_j$ are $\{0.5,50,0,1\}$)

Situation 1: We don't have items and we can buy items worth up to $\hat{P}=1300$. If we buy a sword we have $V(Sword)=0.5*(50+40)*1*1=45$. If we buy a Zeal we have $V(Zeal)=(0.5+0.15)*50*(1+0.2)*1=39$. We know now: It is better to buy a sword than a zeal.

Situation 2: We have a Pickaxe and can spend $1300$ more. So $B_0={Pickaxe}$ and $\hat{P}=875+1300=2175$. Let's test the same two things as above: If we buy a sword we have $V(Sword,Pickaxe)=0.5*(50+40+25)*1*1=57.5$. If we buy a zeal we have $V(Zeal,Pickaxe)=(0.5+0.15)*(50+25)*(1+0.2)*1=58.5$. So in this situation buying a zeal is better.

Situation 3: This is the situation I can't solve and why I'm asking the question. We want to buy both Edge und Hurricane. Which is the optimal order to buy them in? I will give the the examples for only Egde and only Hurricane. As series of maximum prices I take $\hat{P}_n=1000*n$.

Edge
n=1: P=1000 B={}
V(Pickaxe)=37.5
V(Cloak)=30
-> buy Pickaxe
n=2: P=875+1225 B={Pickaxe}
V(Cloak,Pickaxe)=45
-> buy Cloak
n=3: P=875+800+1425 B={Cloak,Pickaxe}
V(Sword,Cloak,Pickaxe)=69
-> buy sword
n=4: P=875+800+1300+1125 B={Sword,Cloak,Pickaxe}
-> combine to edge
V(Edge)=108
Sum of all Bs: 37.5+45+69+108=259.5

Hurricane
n=1: P=1000 B={}
V(Dagger+Dagger+Dagger)=43
V(Dagger+Dagger+Gloves)=40.7
V(Bow)=48.75
-> buy bow
n=2: P=1000+1000 B={Bow}
V(Bow+Dagger+Gloves)=62.25
-> buy dagger + gloves
n=3: P=1000+300+400+1300 B{Bow,Dagger,Gloves}
-> combine to hurricane
V(Hurricane)=76.05
n=4: Do nothing
Sum of all Bs: 48.75+62.25+76.05+76.05=263.1

I guess the best build order is to buy items for Edge and for Hurricane, but I think this example will help to clarify my problem.

I'm happy to hear any ideas and possible solutions. Thanks in advance for your help!

$\endgroup$
  • $\begingroup$ knapsack problem? $\endgroup$ – A. Webb Mar 7 '17 at 18:50
  • $\begingroup$ @A.Webb this might look alike, but I doubt it's applicable, since it has an additive structure. The main problem is that the items in my case influence the worth of other items. I will check if it is possible to reduce my problem to the knapsack problem, but I don't think so. $\endgroup$ – kaetzacoatl Mar 7 '17 at 19:20

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.