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ご覧のとおり、リスト内のオブジェクト間には依存関係（ ）があります。特に、（シリーズの最後の1つ）を持つオブジェクトは、条件がチェックされないid: 4ため、計算から破棄されます。b > 5 and h < 10逆にid: 2、最初に破棄された、のオブジェクトは、id: 3（属性に1を追加することaにより、条件を真にするa > 2）のオブジェクトの結果として計算に含まれます。

N個のオブジェクトを持つ必要な結果を取得するために必要なアルゴリズムは何ですか？

免責事項：提案された構造は単なる例です。結果を達成するためにあなたが信じる変更を提案することができます。私はJavaScript（CoffeeScript）プログラミング言語で作業していますが、他の言語でも問題ありません。

4

1 に答える 1

0

使用できる形式でデータを取得することから始めましょう。データオブジェクトがインスタンス化されたときだけでなく、自由に要件をテストできる必要があります。

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

その間、属性をより便利な状態にしましょう（これは厳密には必要ではありませんが、すべてが簡単になることに注意してください）。

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

次に、最も単純でニーズに合う単純なアルゴリズムについて説明します。基本的に、データセットをループし続け、まだ使用されていない各データセットをテストし、合格した場合は合計に追加します。

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

addと関数を入力させていただきますinit。1addつは単純でなければなりません。2番目のパラメーターの各要素を最初のパラメーターの各要素に追加します。に使用（テストまたは追加）できるinit各要素を設定する必要があります。sum0

于 2012-07-25T04:42:18.790 に答える