0

在一些流行的桌面游戏中，存在一系列 6 个统计数据（也称为属性或能力分数。）它们是整数。就本题而言，它们的数量范围从 7 到 18。

为了公平起见，有一个系统可以让人们“购买”更高的统计数据。这称为点购买。人们从最低限度的所有属性开始（在本例中为 7 个）和一个积分池，然后他们可以花费这些积分来增加他们的属性。但是，这不是 1-1 的比例。18 比 17 贵得多，等等。

我最想做的，是能够编写代码，给定点数和每个属性的成本，为我提供一个随机属性集（7 到 18 之间的 6 个整数），它利用总点数假如。理想情况下，我希望结果接近一致性。

为了使问题更容易思考，我可以提供一个取自 Pathfinder 游戏系统的示例。（请注意，熟悉该系统的人可能会注意到事情并不完全相同。我将其简化为更有意义的计算机科学问题。）

所有属性从7开始，不能再低了。您有 44 点可消费。将属性提高 1 的成本如下： 2,1,1,1,1,1,2,2,3,3,4 或者，如果您更喜欢总成本，2,3,4, 5,6,7,9,11,14,17,21。

也将不胜感激任何类似问题的链接/资源。

4

3 回答 3

1

使用您的示例值提出此问题的另一种方法是：您可以从 {0,2,3,4,5,6,7,9,11,14, 17,21} 使得总和为 44。

一旦你有了这些答案，你就可以统一选择一个，将它们洗牌到你的属性中，每个属性加 7。

一些示例答案：

{21, 21, 2, 0, 0, 0} {21, 17, 6, 0, 0, 0} {21, 17, 4, 2, 0, 0}
{21, 17, 3, 3, 0, 0} {21, 17, 2, 2, 2, 0}

等等

因此，您选择其中之一，例如 {21, 21, 2, 0, 0, 0}。将其混入您的 6 个属性（A 到 F），例如 {21, 0, 0, 2, 21, 0}。将其映射回您的值 {18, 7, 7, 8, 18, 7}。

注意，洗牌并不像听起来那么容易，这里有关于 stackoverflow 的讨论，还有这篇有趣的文章：http ://www.cigital.com/papers/download/developer_gambling.php

这是正确的（我相信），但不一定有效（或漂亮），C++ 来计算你的集合：

#include <vector>
#include <iterator>
#include <iostream>

typedef std::vector<int> Costs;
typedef std::vector<int> Attrs;
typedef std::vector<Attrs> Choices;

void gen(Choices& c, Attrs a, int sum, Costs costs, int attrs) {
  if (sum < 0) { return; }
  if (attrs < 1) {
    if (sum == 0) {
      c.push_back(a);
    }
    return;
  }
  auto cc = costs;
  for (auto cost : costs) {
    a.push_back(cost);
    gen(c, a, sum - cost, cc, attrs - 1);
    a.pop_back();
    cc.erase(cc.begin());
  }
}

Choices genChoices(int sum, const Costs& costs, int attrs) {
  Choices allChoices;
  gen(allChoices, Attrs(), sum, costs, attrs);
  return allChoices;
}


int main(int, char*[]) {
  const Costs costs { 21, 17, 14, 11, 9, 7, 6, 5, 4, 3, 2, 0 };
  const int sum = 44;
  const int attrs = 6;

  auto choices = genChoices(sum, costs, attrs);

  std::cout << choices.size() << "\n";
  for (auto c : choices) {
    std::copy(std::begin(c), std::end(c), std::ostream_iterator<Attrs::value_type>(std::cout, " "));
    std::cout << "\n";
   }

  return 0;
}

使用 g++ 4.7.3 编译：g++ -std=c++0x -Wall -Wextra attrs.cpp

您给出的示例中有 280 个。

于 2013-09-05T05:03:57.940 回答
0

最简单的方法是随机生成所有值，然后检查结果对于给定数量的点是否可行。如果没有重新开始。

这可能看起来非常低效，在某种程度上它当然是，但对于实际应用程序来说这完全没问题。例如，如果选择可行解决方案的机会为 1/6，则预期尝试次数为 6，您需要尝试 40 次以上的机会小于千分之一。

因此，除非您需要大量执行此操作（至少 > 1000 次），否则我会推荐此方法。它易于编码、简短并且适用于任何参数。

两个加速：

  1. 如果您的可用点数较少，则仅生成可以通过极端放置属性购买的范围内的属性。所以如果你有10个点，只生成7-14范围内的属性。
  2. 您可以在生成属性时检查当前结果是否可行。因此，如果在前两个属性上花费的分数超过了可能的分数，则您已经可以丢弃当前结果。丢弃当前配置并重新开始非常重要。如果你试图以某种方式修复它，你最终会得到一个倾斜的分布。

* *编辑：刚刚意识到我错过了你所说的“所有积分花费”条件。这使问题变得更加困难，并且这种方法非常低效，因为只有很小一部分可能的配置是可行的。确切的动态取决于您的参数，因此如果您只需要少量样本，您可以尝试这种方法，看看它是否足够快。

于 2013-09-05T01:02:47.387 回答
0

对于这里涉及的一般理论：可能的配置是对背包问题的修改。要统一采样，您可以迭代所有可行的配置并选择然后统一选择其中一个。我希望可行配置的数量相当少，所以如果你有一种快速找到它们的方法，那可能会很好。

如果可能的配置太多而无法枚举或计数，那么您就有一个标准问题，即从您有一些信息但不是全部信息的分布中抽样。我认为解决这个问题的标准方法是使用Metropolis-Hastings 算法或其他类型的 Markov Chain Monte Carlo（另请参见Propp-Wilson Algorithm）。但是要使用这些方法，您必须在具有某些属性的可行状态之间构造一个转换函数。我试了一点，布特想不出一个。

于 2013-09-05T02:37:57.553 回答