代码之家 › 专栏 › 技术社区 › abc

按顺序生成约束集

abstract set algorithm

abc · 技术社区 · 6 年前

首先,我将粘贴场景,然后提出我的问题:

假设您有一个类别列表,例如:

Food,Meat,Dairy,Fruit,Vegetable,Grain,Wheat,Barley

现在,您有了一个符合上面列出的一个或多个类别的项目列表。

以下是项目的示例列表: Pudding,Cheese,Milk,Chicken,Barley,Bread,Couscous,Fish,Apple,Tomato, Banana,Grape,Lamb,Roast,Honey,Potato,Rice,Beans,Legume,Barley Soup

正如您所看到的,每个项目都至少适合一个类别,它可以适合更多的项目,或者可能是所有的项目,但最小值总是一个。

例如 Cheese 是一个 Food 和 Dairy .

每个项目有两个属性:
1)价格标签
2)随机值

集合被定义为将每个类别映射到一个项。
换句话说,所有类别都必须在一个集合中出现。

上述项目中的一组可以是:

[Pudding,Lamb,Milk,Apple,Tomato,Legume,Bread,Barley Soup]

如您所见,每个项目都映射到一个类别槽:

布丁被映射到食物类别
羊肉被映射到肉类类别
牛奶被映射到乳制品类别
苹果被映射到水果类别
番茄属于蔬菜类
豆类被映射到谷物类别
面包被映射到小麦类别
大麦汤被映射到大麦类别

我的问题是,从给定的项目列表中按照上述类别的顺序集生成最有效的算法是什么?

最佳集合被定义为总的随机值最高。

唯一的限制是任何生成的集合总不能超过某个固定金额,换句话说,所有生成的集合都应该在这个价格上限内。

希望我明白,谢谢!

3 回复 | 直到 6 年前

miradham 6 年前

好吧,这是我第二次尝试回答这个问题。

假设我们有以下输入

class Item {
public:
    // using single unsigned int bitwise check sets
    unsigned int category;
    int name;
    int value;
    int price;
...
};

class ItemSet
{
public:
    set<Item> items;
    int sum;
};

首先,根据最高随机值,然后是最低价格对输入数据进行排序

bool operator<(const Item& item1, const Item& item2) {
    if (item1.value == item2.value) {
        if (item1.price == item2.price) {
            return item1.name < item2.name;
        }
        return item1.price > item2.price;
    }
    return item1.value < item2.value;
}
...
vector<Item> v = generateTestItem();
sort(v.begin(), v.end(), greater<Item>());

接下来,使用backtracking将顶级集收集到堆中,直到满足条件为止。在我们的回溯算法中对输入数据进行排序,可以确保所收集的数据是基于最高的 value 最低 price . 还有一件事要注意,我比较了项目类别( currentCats )通过位操作 O(1) 复杂性。

priority_queue<ItemSet> output;
void helper(vector<Item>& input, set<Item>& currentItems, unsigned int currentCats, int sum, int index)
{
    if (index == input.size()) {
        // if index reached end of input, exit
        addOutput(currentItems);
        return;
    }
    if (output.size() >= TOP_X) {
        // if output data size reached required size, exit
        return;
    }
    if (sum + input[index].price < PRICE_TAG) {
        if ((input[index].category & currentCats) == 0) {
            // this category does not exists in currentCats
            currentItems.insert(input[index]);
            helper(input, currentItems, currentCats | input[index].category, sum + input[index].price, index + 1);
        }
    } else { 
        addOutput(currentItems);
        return;
    }
    if (currentItems.find(input[index]) != currentItems.end()) {
        currentItems.erase(input[index]);
    }
    helper(input, currentItems, currentCats, sum, index + 1);
    return;
}

void getTopItems(vector<Item>& items)
{
    set<Item> myset;
    helper(items, myset, 0, 0, 0);
}

在最坏的情况下,这种回溯将运行o(2^n)复杂性,但由于 TOP_X 是有限的价值,它不应该花费太长的时间。

我试图通过生成随机值来测试这段代码,它看起来工作正常。可以找到完整的代码 here

Robindar 6 年前

您试图实现的是一种最大匹配的形式,我不知道是否有一种有效的方法来计算顺序集,但是这种减少可能会帮助您。

定义一个二部图,其中一侧为每个类别一个节点,另一侧为每个项目一个节点。如果某个项属于某个类别,则在该项和该类别之间添加一条边,其权重由该项的随机值定义。

您定义的“集合”是该图中最大的基数匹配。它们可以在合理的时间内被列举出来,正如Takeaki Uno在 “ A Fast Algorithm for Enumerating Non-Bipartite Maximal Matchings “,在您的情况下,它可能更快,因为您的图是二部的。

在这些集合中,您正在寻找具有最大权重和价格限制的集合。根据您的数据,只需枚举所有数据,根据价格筛选它们,如果没有太多结果,则对剩余结果进行排序就足够了。

如果不是这样的话,那么你可以通过求解目标函数为总权重,约束条件为限价和基数的组合优化问题来找到最佳的集合(在小企业中称为最大加权匹配)。当你用这种形式写问题时,甚至可能已经有在线的解决方案了。然而,这将只提供一个这样的集合,而不是一个排序列表,但是由于这个问题在一般情况下是非常困难的,所以这是您所能期望的最好的。为了获得更好的结果,您需要对数据进行更多的假设(例如,这些集合的最大数目的界限、可以属于k个以上类别的最大项目数等)。

Old Pro 6 年前

我不太清楚你所说的“按顺序生成”是什么意思。

我认为任何算法都会生成集合,给它们打分,然后尝试生成更好的集合。考虑到所有的约束条件,我认为您不能一次有效地生成最佳集。

0-1 knapsack problem 已经证明 NP-hard 这意味着没有已知的多项式时间(即O(n^k))解。如果在你的输入中,随机数总是等于价格,并且只有一个类别,那么这个问题和你会遇到的问题是一样的。换句话说,你的问题至少和背包问题一样困难,所以你不能期望找到一个有保证的多项式时间解。

您可以使用嵌套循环轻松地组合生成所有有效集:按类别循环,循环该类别中的项。在早期,你可以通过跳过一个已经被选中的项目来提高效率,一旦你发现超过了价格上限,你可以跳过整个项目。将这些结果放在一个堆中,然后您可以按顺序将它们吐出来。

如果你的问题是你想要比那更好的性能,在我看来更像是 constraint programming 或者更具体地说, constraint satisfaction 问题。我建议你看看处理这些问题的技巧。