确保对象进入正确的桶

Question

我有这些独一无二的物品。

items = [1, 2, 3, 4, 5, 6, 7, 8]

Buckets 目前显示了每个项目可能去向的可能性。物品只能去允许的地方。

possiblebuckets = [
  [1, 6, 3, 4], [7, 3, 6], [5, 3, 1], [3, 2, 4], [2], [2], [2, 3]
]

我希望每个桶有 1 个项目。我想确保我可以将物品放入桶中，以便将最大数量的物品放入桶中。如果某些项目无法放入桶中或某些桶仍然是空的，这没关系。

结果应该是：

finalbuckets = [
  [6], [7], [1], [4], [2], [], [3]
]

例如，一种天真的做法：

      items.forEach(function (item) {
        var findMatch = possiblebuckets.filter(function (bucket, i) {
          return bucket.includes(item)
        });

        findMatch.length = 0
        findMatch.push(item);
      });

导致项目未放入最佳存储桶。

Answer 1

好的，这是我的解决方案：

      var oneLevelDeepClone = function (obj) {
        return obj.map(function (bucket) {
          return bucket.map(function (item) {
            return item
          })
        })
      }

      var maxDeployments;
      var maxDeploymentsCount = 0;

      function constraintProblem (tempBuckets) {
        const tryAgain = [];

        var iterativeTempBuckets = oneLevelDeepClone(tempBuckets)
        var innerTempBuckets = oneLevelDeepClone(iterativeTempBuckets)
        innerTempBuckets.forEach(function (bucket, bucketIndex) {
          var keep = bucket.shift();
          if (bucket.length) {
            // worth a try
            bucket.forEach(function (item) {
              var newAttempt = oneLevelDeepClone(innerTempBuckets)
              newAttempt[bucketIndex] = [item]
              tryAgain.push(newAttempt);
            })
          }

          if (keep) {
            // keep 1 and toss the others, then remove that one from the other buckets
            innerTempBuckets[bucketIndex] = [keep]
            innerTempBuckets.forEach(function (iterativeBucket, iterativeBucketIndex) {
              if (bucketIndex != iterativeBucketIndex) {
                if (iterativeBucket.indexOf(keep) != -1) {
                  iterativeBucket.splice(iterativeBucket.indexOf(keep), 1)
                }
              }
            })
          }
        })

        var counter = 0;
        innerTempBuckets.forEach(function (bucket) {
          if (bucket[0]) counter++
        })
        if (counter > maxDeploymentsCount) {
          maxDeploymentsCount = counter;
          maxDeployments = innerTempBuckets;
        }

        if (tryAgain.length) {
          tryAgain.forEach(function (anotherTry) {
            constraintProblem(anotherTry);
          })
        }
      }

possiblebuckets = [
  [1, 6, 3, 4], [7, 3, 6], [5, 3, 1], [3, 2, 4], [2], [2], [2, 3]
]
      constraintProblem(possiblebuckets)

console.log(maxDeployments);

<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.17.15/lodash.min.js"></script>

<pre id="results"></pre>

确保对象进入正确的桶

ensuring objects go into the right bucket

javascript

constraint-programming