寻找最便宜元素以获得一定数量资源的算法

Question

我正在寻找一种算法，它能够找到最便宜和最有效的方式来购买资源。

示例数据(让我们以含有矿物质的岩石为基础)

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)

每个单位的成本为 1。因此，一 block 石头的成本为内部单位的总和。

案例:

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

我可以用什么算法来估计需要哪种类型的岩石来支付最低的单价(尽可能低的损失)。

在这种情况下，我想出了一个算法来计算每个项目的浪费 Material 与所需 Material 的比率。
在 Iron 的情况下，仍然比率可以使我获得摇滚 F。因为那将是最便宜的比率。但石头的整体值(value)很大。并且可以用值(value)较低的石头来实现，因为我不需要 30 000 单位的铁。

其次，而且要复杂得多。就是将所有 3 种情况结合起来，以最低的价格(浪费)获得满足所有要求的最佳 gem 组合。

Answer 1

这是无界背包问题，但您需要的不是最大化，而是最小化。你需要的资源量就是“重量”，成本就是“值(value)”。

这些是重写的属性:

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

其中 m[j] 是 j 资源量的解决方案，v[i] 是 的成本第 i 个 岩石。

这是一些伪代码:

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

你所说的贪婪方法会给你一个次优的解决方案。