用于确定共享项的集合之间（最多）剩余多少项的算法

问：

假设我们想从 4 组 S1-S4 中获取物品。这些集合在它们之间共享项目。一些示例集是：

S1 = ['b1'];
S2 = ['b1', 'b2'];
S3 = ['b1', 'b2', 'b3'];
S4 = ['b1', 'b2', 'b3', 'b4'];

很明显，如果你从 （） 中选择一个项目，那么你只能从 、2 和 3 中选择 1 个项目。S1b1S2S3S4

但是，如果你从中选择一个项目，那么在下一步中，你可以从中选择所有项目，或者从中选择所有项目，或者从中选择所有项目，仅仅是因为算法必须足够聪明，知道有一个组合（例如，分配自），这将允许从其他集合中获得更高的最大自由元素（通过选择，你有最大自由3 in ， 2 英寸和 1 英寸S4S1S2S3b4S4b4S3S2S1)

换句话说，当你从一个集合中占据一个元素时，算法不应该占据一个特定的元素，而是应该足够聪明，知道可以从其他集合中占据多少个元素（最大数量），前提是这些项目是以智能方式选择的。

演示它应该如何工作（绿色 = 可用，红色 = 占用，橙色 = 由于另一组占用而占用）：

另一个演示：

（注意，算法发现 S5 有 3 个唯一元素，因此任何其他集合都是完全免费的）

还有另一个：

（请注意，该算法理解，如果您从 S5 中选择所有 4 个，那么您必须放弃其他类别中的一个）

另一个：

（如果您从中挑选 3 个项目，您将不得不放弃 1 个项目，现在您最多只能从中挑选 2 个元素。 请注意，中占用的项目不是特定元素，它是 要么是 ，没关系，我只对我现在可以从中挑选的最大元素数量感兴趣）S5S2S2b1b7

以上所有方法都适用于我的算法，但在其他情况下会失败。

到目前为止我尝试过的（代码，但欢迎任何语言解决方案）：nodejs

var allCategories = [];

const process = require('process');

Reset = '\x1b[0m'
FgRed = '\x1b[31m'
FgGreen = '\x1b[32m'
FgYellow = '\x1b[33m'

function getCommonCount(s1, s2) {
    return s1.filter((n) => s2.includes(n)).length;
}

var categories = {};
var common = {};
function processCategories() {
    categories = {};
    for (var i in allCategories) {
        categories[i] = {
            total: allCategories[i].length,
            occupied: 0,
            dueTo: {},
            totalDue: 0
        };

        common[i] = {};

        for (var j in allCategories) {
            if (i === j) {
                continue;
            }
            common[i][j] = getCommonCount(allCategories[i], allCategories[j]);
        }
    }
}

function occupy(countToOccupy, categoryId) {
    console.log('OCCUPY', countToOccupy, 'from', categoryId);

    var category = categories[categoryId];
    var free = category.total - category.occupied;

    if (free < countToOccupy) {
        console.log('Cannot occupy that many elements of type', categoryId);
        return false;
    }

    category.occupied += countToOccupy;

    for (var otherCategoryId in common[categoryId]) {
        var commonCount = common[categoryId][otherCategoryId];

        var atLeastThatMustOccupied =  (category.occupied + commonCount) - category.total;

        if (atLeastThatMustOccupied < 0) {
            continue;
        };

        var otherCategory = categories[otherCategoryId];

        if (otherCategory.occupied < atLeastThatMustOccupied) {

            var countToOccupyOtherCategory = atLeastThatMustOccupied - otherCategory.occupied;

            otherCategory.occupied += countToOccupyOtherCategory;

            if (!otherCategory.dueTo.hasOwnProperty(categoryId)) {
                otherCategory.dueTo[categoryId] = 0;
            }

            otherCategory.dueTo[categoryId] += countToOccupyOtherCategory;
            otherCategory.totalDue += countToOccupyOtherCategory;
        }
    }

    return true;
}

function deoccupy(countToDeoccupy, categoryId) {
    console.log('DEOCCUPY', countToDeoccupy, 'from', categoryId);
    var category = categories[categoryId];

    var reallyOccupied = (category.occupied - category.totalDue);

    if (reallyOccupied < countToDeoccupy) {
        console.log('There are not that much really occupied thingies here so as to deoccupy them');
        return false;
    }

    category.occupied -= countToDeoccupy;

    for (var otherCategoryId in common[categoryId]) {

        if (!categories[otherCategoryId].dueTo.hasOwnProperty(categoryId)) {
            continue; // no elements set due to the parent category
        }

        var dueToNumber = categories[otherCategoryId].dueTo[categoryId];

        var countToRemove = Math.min(countToDeoccupy, dueToNumber);

        if (countToRemove === dueToNumber) {
            // remove the dueTo field
            delete categories[otherCategoryId].dueTo[categoryId];
        } else {
            categories[otherCategoryId].dueTo[categoryId] -= countToRemove;
        }

        categories[otherCategoryId].totalDue -= countToRemove;
        categories[otherCategoryId].occupied -= countToRemove;
    }

    return true;
}

function visualizeCategories() {
    process.stdout.write(Reset);

    console.log()
    for (let categoryId in categories) {
        var category = categories[categoryId];
        var reallyOccupied = (category.occupied - category.totalDue);
        var free = category.total - category.occupied;
        process.stdout.write(FgGreen + categoryId + ' ');
        process.stdout.write(FgRed + '0'.repeat(reallyOccupied));
        process.stdout.write(FgYellow + '0'.repeat(category.totalDue));
        process.stdout.write(FgGreen + '0'.repeat(free));
        console.log()
    }

    console.log(Reset);
}

allCategories = {
    S1: ['b1'],
    S2: ['b1', 'b2'],
    S3: ['b1', 'b2', 'b3'],
    S4: ['b1', 'b2', 'b3', 'b4'],
    S5: ['b5', 'b1', 'b7', 'b8']
};

console.log('CATEGORIES:');
console.log(allCategories);

processCategories();

occupy(1, 'S1'); visualizeCategories();
occupy(3, 'S5'); visualizeCategories();
occupy(1, 'S2'); visualizeCategories();
occupy(1, 'S3'); visualizeCategories();

deoccupy(3, 'S5'); visualizeCategories();
deoccupy(1, 'S1'); visualizeCategories();
deoccupy(1, 'S3'); visualizeCategories();
deoccupy(1, 'S2'); visualizeCategories();


allCategories = {
    S1: ['b1'],
    S2: ['b1', 'b2'],
    S3: ['b2']
};

console.log('CATEGORIES:');
console.log(allCategories);

processCategories();

occupy(1, 'S1', true); visualizeCategories();
occupy(1, 'S3', true); visualizeCategories();

代码解释：分析可视化的类别并创建我用来弄清楚需要占用和取消占用的内容的数据结构以及调用。数据结构如下所示：processCategoriesoccupydeoccupy

category = { // or "set" of items
    total: // NUMBER: total entries of this set
    occupied: // NUMBER: how many elements of this set are occupied, either directly or indirectly
    dueTo: // OBJECT {categoryId -> number}: how many elements of this set are indirectly occupied and due to which category. (e.g. dueTo = {S1: 1, S3: 1} means 1 occupied indirectly through S1 and 1 indirectly through S3)
    totalDue: 0 // NUMBER: sum of the dueTo entries
};

笔记：

• 类别处理创建对象，该对象本质上是一个二维数组，它保存了类别具有的公共元素数量。（例如commoncommon['S1']['S2'] === 4)
• occupied - totalDue给出直接占用的（红色）条目。

• 为了占用条目，我使用

  var atLeastThatMustOccupied = (category.occupied + commonCount) - category.total;

在某些情况下似乎有效，但在其他情况下则不起作用。

• dueTo用于取消占用条目。

在第一个图像中，代码工作正常，在此示例中，代码失败：

在最坏的现实场景中，每个集合最多可以有 300 个项目，最多有 10 个集合，并且算法应该足够快（希望在普通 cpu 中< 1s），以确定可以从所有集合中选取多少个项目。此外，该算法应该能够取消占用项目，例如做相反的事情 - 从集合中删除一个项目，并确定现在可以从其他集合中挑选多少个项目。

假设只有当元素直接从该集合中占用时，才能从该集合中取消占用该元素。（例如，如果 S3 = ['b1'， 'b2'， 'b3'] 并且其所有元素都被间接占用，则无法调用 de-occupy 从 S3 中删除元素）