时间戳

首页 > 解决方案 > 制作资源的有效分配

c# - 制作资源的有效分配

问题描述

我正在制作一个游戏，您可以在其中制作各种物品。资源有限，我需要根据可用资源计算每个项目的最大制作次数。除了算法的最后一部分，我一切正常。

首先，假设我们正在计算我们可以种植的最大胡萝卜数量。种植 1 根胡萝卜的配方有多个步骤：

胡萝卜：消耗 1 水，使用 1 块农田

水：使用 1 个桶，使用 1 个池塘

桶：消耗 7 个木材

农场地块：消耗 2 个木材，消耗 1 个土壤

土壤：使用 1 个铲子，使用 1 个泥坑

铲子：消耗 2 个木材

如果不清楚：为了种植胡萝卜，我们在农田里加了一桶水。为了获取水，我们在池塘上使用水桶。每个桶由 7 块木头制成。每个农场地块由两块木头和一块土壤制成…… 等等。如果我们“消费”一件物品，它的所有用途都会立即耗尽。但是，如果一件物品被“使用”过，它在生产过程中只会失去 1 次使用。例如，一个农场可以使用 4 次来种植胡萝卜，然后才被摧毁。假设这些物品具有以下用途：

胡萝卜：1次

水：1 次使用

铲斗：15 次使用

农场地块：4 次使用

土壤：1 次使用

铲子：20 次使用

木材：1 次使用

所以，这就是我卡住的地方：注意配方的多个部分需要木材。为简单起见，让我们假设我们可以取 100 块木头。我需要一种方法来计算应该为配方的每个部分分配多少木材。目前，我正在这样做：（woodUsesInStep / totalWoodUses）* amountOfWood。所以，如果我们看看桶里有多少木头，它会是：(7 / 11) * 100 = ~64 块木头。问题是这不会产生最多的胡萝卜……

使用此算法，我得到以下结果：

桶：分配 64 块木材，9 桶制成

铲子：分配了 18 个木头，制作了 9 个铲子

农场地块：分配了 18 块木材，制作了 9 块农场地块

最终结果：可以制作 36 根胡萝卜

但这是我想要的结果：

桶：49 个木头，7 个桶

铲子：4 个木头，2 个制成的铲子

农场地块：46 块木头，23 块农场地块

最终结果：可以制作 92 个胡萝卜

不知何故，我需要确定配方的哪一部分产生更高的结果并根据它分配木材，但我目前不知道如何去做。

标签： c#algorithmmath

解决方案

正如您已经发现的那样，您当前的公式使用配方中每种资源（“成分”）的成本来计算如何使每种成分的数量相等。（你可以用 100 块木头做 9 个桶、9 个铲子和 9 个农田。）它没有考虑每种成分的价值，即（1）配方需要每种成分的多少和（ 2）成分在食用前可以使用多少次。

您已经手动确定了这一点，并且您可能遵循了类似于以下的步骤。您已经知道消耗木材的三种成分是水桶、铲子和农田。要确定它们在您的配方中应如何加权，您需要确定每种胡萝卜消耗的每种成分的数量。您需要递归地执行此操作，因为某些成分是使用其他成分制作的。

当您计算需要多少时，请记住某些成分可以多次使用，因此您可能不会消耗全部成分。例如，如果您需要 1 个存储桶，但该存储桶有 15 次使用，那么您实际上消耗了一个存储桶的 1/15。如果这部分令人困惑，请考虑 100 个胡萝卜。如果你需要用 100 次桶装 100 根胡萝卜，而一个桶在被消耗之前可以使用 15 次（那么你需要建造更好的桶！），你需要 100/15 桶，或者 6 2/3 桶。这就像说每个胡萝卜消耗 1/15 桶一样，因为 1/15 * 100 = 6 2/3。

1 Carrot requires:
1 Water/1 use = 1 Water
1 Farm Plot/4 uses = 1/4 Farm Plot

*** First recursion ***

1 Water requires:
1 Bucket/15 uses = 1/15 Bucket
1 Pond (not applicable to this calculation)

1 Farm Plot requires:
2 Wood/1 use = 2 Wood
1 Soil/1 use = 1 Soil

*** Second recursion ***

1 Bucket requires:
7 Wood/1 use = 7 Wood

1 Soil requires:
1 Shovel/20 uses = 1/20 Shovel
1 Dirt Pit (not applicable to this calculation)

*** Unwinding the recursion ***

*** First recursion ***

1 Water requires:
1/15 Bucket

1 Farm Plot requires:
2 Wood
1 Soil -> 1/20 Shovel

*** Initial ***

1 Carrot requires:
1 Water -> 1/15 Bucket
1/4 Farm Plot -> 1 Farm Plot = {2 Wood + 1/20 Shovel} -> 1/4 * (2 Wood + 1/20 Shovel ) -> 1/2 Wood + 1/80 Shovel

所以 1 根胡萝卜需要：

1/15 Bucket (1 Bucket = 7 Wood, so 1/15 Bucket = 7/15 Wood)
1/4 Farm Plot (1 Farm Plot = 2 Wood, so 1/4 Farm Plot = 2/4 or 1/2 Wood)
1/80 Shovel (1 Shovel = 2 Wood, so 1/80 Shovel = 1/40 Wood)

现在让我们回到原来的公式，即woodUsesInStep / totalWoodUses * amountOfWood。对于 Bucket，您对 woodUsesInStep 使用值 7，对 totalWoodUses 使用 11，但现在您可以看到，woodUsesInStep 实际上是 Bucket 的 7/15，Farm Plot 的 1/2，Shovel 的 1/40，这意味着 totalWoodUses 是 119/120 (7/15 + 1/2 + 1/40)。

现在我们可以应用公式：

Bucket: (7/15) / (119/120) * 100 = 47.1 Wood (makes 6.7 Buckets)
Farm Plot: (1/2) / (119/120) * 100 = 50.4 Wood (makes 25.2 Farm Plots *assuming you have enough Shovels!*)
Shovel: (1/40) / (119/120) * 100 = 2.5 Wood (makes 1.25 Shovels)

正如您将其与预期结果进行比较时所看到的那样，这让您非常接近。事实上，这确实为您提供了配方中木材的正确分布，但不幸的是，这只是问题的前半部分。由于您不能花费 2.5 个木材或制作 1.25 个铲子，因此您需要一种方法来确定每种成分是向上还是向下取整。我没有这部分的确切公式，但我相信这会让你非常接近：

  1. 从您制作最少的成分开始。（在这种情况下，它是铲子）。
  2. 四舍五入到最接近的成分数量，并从您的总可用资源中减去成本。（在这种情况下，您将 1.25 舍入到 2 个完整的铲子，然后从 100 个总数中减去 4 个木材的成本，剩下 96 个可用。
  3. 对每种成分重复这些步骤，直到用完资源：
  4. 下一个成分是桶，因为您要制作 6.7 个桶，而不是 25.2 个农场地块。
  5. 四舍五入到 7 个桶并从剩余的 96 个木材中减去 49 个木材的成本，剩下 47 个可用。
  6. 下一个（也是最后一个）成分是农场地块。您希望将 25.2 向上舍入为 26，但您的资源仅够 23，因此请制作这些。

结果：

2 Shovels
7 Buckets
23 Farm Plots
92 Carrots, as expected

成功！

推荐阅读