Action executed in 0.000

Non-idled CPU and Maximizing Profit

I'm finally putting my computer to the work it can do. Instead of sitting around idle, the CPU -- well one of them -- is at maximum load. I wrote a program to pick which items i should build in WoW, given all the items i have, and recipes i know.

It's not that intelligent. Basically it uses a brute force approach. But just like this even 40 items in my bag would take 8 minutes to run.

Then i realized i was solving the same sub-problem more than once. For example let's say that with the items, say 13 copper bars, you have you can build an axe, a mace, a sword, a dagger, and a ring. First you choose to build the axe, which requires 6 copper bars. Assuming you built the axe, from the items you have left (7 copper bars) let's assume you can build a sword, a dagger, and a ring. There isn't enough copper to build a mace (8 copper bars). You first pick the sword (4 copper bars) and build it. Now you have even less resources (3 copper bars). Let's say all you can build is 3 rings. So it's important to remember that with 3 copper bar, all you can build is 3 rings.

Some time later you will you will get back to the stage when you had 13 bars and you're up to trying the 3 item on your list, the sword. Then you build an axe. Now your at that point again with 3 copper bars. Well you've solved this problem already. You know the answer is 3 rings. So just return that answer.

After incorporating this technique, called memoization, my program became much faster.

Despite this. After adding 30 new recipes and 10 more items, it is once again taking a long time to complete.


none yet

Post a Comment

* indicates a required field
anonymous (If you want to identify yourself, please sign in first.)
required This field is required.

Max size is 2 MB, aspect ratio 3:4 width:height
required This field is required.
Please include a short description.
required This field is required.

480 characters remaining.
is public

(Use this field if you have to. 3000 characters remaining.)
1 dime, 1 quarter + 100

Trackback URL