CODEWITHSUNDEEP
algorithmmath
Grzegorz
Grzegorz

Reputation: 3608

Algorithm to find cheapest items to get certain amount of resources

I'm looking for an algorithm, that would be able to find cheapest and most efficent way to buy resources.

Example data (Let's base this on rocks that contain minerals)

Rock A (Contains 300 units of iron, 200 units of copper, 500 units of silver)
Rock B (Contains 150 units of iron, 400 units of copper, 100 units of silver)
Rock C (Contains 180 units of iron, 300 units of copper, 150 units of silver)
Rock D (Contains 200 units of iron, 350 units of copper, 80 units of silver)
Rock E (Contains 220 units of iron, 150 units of copper, 400 units of silver)
Rock F (Contains 30 000 units of iron, 150 units of copper, 400 units of silver)

Each unit costs 1. So A rock costs a sum of units inside.

Cases:

First case, needs 2600 units of Copper
Second case needs 5000 units of Iron
Third case needs 4600 units of Silver

What algorithm could I use to estimate which types of rocks are needed to pay lowest unit price (have as low loss as possible).

That case I came up with an algorithm that would calculate for each item a ratio of wasted vs needed materials.
Still ratio could lead me to getting rock F in case of Iron. Since that would be cheapest ratio. But overall value of stone is big. And could be achived with lower value stones as I dont need 30 000 units of Iron.

Secondly, and way more complex. Is to combine all 3 cases and get best combination of stones to fit all requirements at lowest price (waste).

Upvotes: 0

Views: 408

Answers (2)

imreal
imreal

Reputation: 10378

This is the unbounded Knapsack problem but instead of maximization, you need minimization. The amount of resource you need is the "weight" and the cost is the "value".

These are the re-written properties:

m[0] = 0
m[w] = min(v[i] + m[w - w[i]]) for w[i] < w

Where m[j] is the solution for j amount of resource and v[i] is the cost of the ith rock.

Here is some pseudocode:

m[0] = 0
for i = 1 to W: # W is your target amount of resource i.e. 2600, 500, 4600
    minv = max_value_possible
    # rocks is the vector with the <cost,resource> pairs of each rock e.g.<650,150>
    # for Rock B, iron
    for r in rocks:
        if r.second < i: minv = min(minv, m[i - r.second] + r.first)
    m[i] = minv

Knapsack problem

The greedy approach you're talking about will give you a suboptimal solution.

Upvotes: 3

t3s0
t3s0

Reputation: 282

In my opinion, it will be the best way if you follow your first idea. The percentage of a mineral in relation to the overall amount gives you the best result:

For example if you search for the mineral iron:

Rock A: 300/1000 = 30% iron

Rock F: 30000 / 30550 = 98.2% iron

Upvotes: 0

Related Questions