0

考虑以下情况：

items = [
  {
    id: 1
    attributes: [
      { key: a, value: 2 }
      { key: b, value: 3 }
    ],
    requirements: null
  }
  {
    id: 2
    attributes: [
      { key: b, value: 2 }
    ],
    requirements: a > 2
  }
  {
    id: 3
    attributes: [
      { key: a, value: 1 }
      { key: c, value: 1 }
    ],
    requirements: a > 1 and b > 2
  }
  {
    id: 4
    attributes: [
      { key: a, value: 2 }
      { key: d, value: 7 }
    ],
    requirements: b > 5 and h < 10
  }
]

将各种加在一起（总和）的预期结果attributes是：

result = [
  { key: a, value: 3 }
  { key: b, value: 5 }
  { key: c, value: 1 }
]

如您所见，requirements列表中的对象之间存在依赖关系 ( )。特别是，具有id: 4（系列中的最后一个）的对象从计算中被丢弃，因为b > 5 and h < 10从未检查过条件。相反，带有 的对象id: 2最初被丢弃，然后作为带有 的对象的结果落入计算中id: 3（通过将 1 加到属性a中，使条件为真a > 2）。

获得具有 N 个对象的所需结果所需的算法是什么？

免责声明：建议的结构只是一个例子。您可以提出任何您认为可以实现结果的更改。我正在使用 JavaScript (CoffeeScript) 编程语言，但其他任何语言都可以。

4

1 回答 1

0

Let's start by getting the data in a format we can use. We need to be able to test requirements at will, instead of only when the data object is instantiated:

  {
    id: 4
    attributes: [
      { key: a, value: 2 }
      { key: d, value: 7 }
    ],
    requirements: (sum) -> sum.b > 5 and sum.h < 10
  }

While we're at it, let's get the attributes in a more useful state (note that this isn't strictly necessary, but makes everything simpler):

  {
    id: 4
    attributes: {
      a: 2
      d: 7
    },
    requirements: (sum) -> sum.b > 5 and sum.h < 10
  }

Now I'll go through the naive algorithm, which is simplest and should fit your needs. Essentially, we'll keep looping over the data set, testing each one that hasn't been used yet and adding it to the sum if it passes.

changed = true
sum = {}
init(sum, items)
while changed
    changed = false
    for item in items
        if !item.used && item.requirements(sum)
            add(sum, item.attributes)
            changed = true
            item.used = true

I'll let you fill in the add and init functions. The add one should be simple; it adds each element in the second parameter to each element in the first. The init needs to set each element in sum that may be used (tested or added to) to 0.

于 2012-07-25T04:42:18.790 回答