查找具有非冲突类别的项目子集

Question

我有一个对象列表，每个项目都有一个成本和一组与之关联的资源（见下文）。我正在寻找一种方法 select 基于合并成本的此列表中的一个子集，并且每个资源最多只能包含一次（尽管并非每个资源都必须包含）。计算子集的组合成本的方式应该是可交换的（例如最大、最小、平均）。如果两个子集具有相同的组合成本，则具有更多项目的子集是 selected。

 Item  |  cost   resources [1..3]
 ================================
  P1   |  0.5          B
  P2   |   4         A B C
  P3   |  1.5        A B
  P4   |   2             C
  P5   |   2         A

这将允许这些组合：

 Variant  |   Items    sum
 ==========================
    V1    |  P1 P4 P5  4.5
    V2    |     P2      4
    V3    |   P3 P4    3.5

最大 selection V1 将被 selected。物品的数量可以从1个到几十个不等，资源的数量也是如此。

我的蛮力方法只是总结所有可能排列的成本和 select max/min 排列，但我认为有一种更有效的方法可以做到这一点。我在 Java 8 中编码，但我可以使用伪代码或 Matlab。

我发现了一些看似相似的问题（即 (1), (2), (3)），但我无法将它们完全转移到我的问题中，如果您认为这是重复的，请原谅我：/

提前致谢！ ~

澄清

我的一个朋友对我想要什么样的套装感到困惑。不管我最终 select 我的子集如何，我总是想生成包含尽可能多的项目的子集。如果我已经将 P3 添加到我的子集中并且可以添加 P4 而不会产生冲突（也就是说，资源在子集中使用了两次）那么我想要 P3+P4，而不仅仅是 P3。

澄清2

"Variants don't have to contain all resources" 意味着如果不可能在不产生冲突的情况下添加一个项目来填充缺失的资源槽（因为所有具有缺失资源的项目也已经存在另一个资源）那么子集是完整的.

Answer 1

这个问题是NP-Hard, even without the "Resources" factor, you are dealing with the knapsack-problem。

如果您可以将成本转换为相对较小的整数，则可以通过为每个分配的资源增加一个维度来修改 Knapsack 的动态规划解决方案，并有一个类似于（显示概念，确保所有边缘情况工作或根据需要修改）：

D(_,_,2,_,_) = D(_,_,_,2,_) = D(_,_,_,_,2) = -Infinity
D(x,_,_,_,_) = -Infinity   x < 0
D(x,0,_,_,_) = 0 //this stop clause is "weaker" than above stop clauses - it can applies only if above don't.
D(x,i,r1,r2,r3) =  max{1+ D(x-cost[i],i-1,r1+res1[i],r2+res2[i],r3+res3[i]) , D(x,i-1,r1,r2,r3)}

其中 cost 是成本数组，res1,res2,res3,... 是每个项目所需资源的二进制数组。

复杂度将为 O(W*n*2^#resources)

Answer 2

在对我的问题进行了更多思考之后，我想出了一个让我感到非常自豪的解决方案。此解决方案：

将找到所有可能的完整变体，即在不引起冲突的情况下无法添加其他项目的变体
还会发现一些不完整的变体。我可以接受。
可以 select 以任何方式得到最终变体。
适用于非整数项目值。

我意识到这确实不是背包问题的一个变体，因为物品有一个值但没有与之相关的重量（或者，你可以将其解释为多维背包问题变体的变体，但所有权重都相等）。该代码使用了一些 lambda 表达式，如果您不使用 Java 8，则必须替换它们。

public class BenefitSelector<T extends IConflicting>
{
public ArrayList<T> select(ArrayList<T> proposals, Function<T, Double> valueFunction)
{
    if (proposals.isEmpty())
        return null;


    ArrayList<ArrayList<T>> variants = findVariants(proposals);

    double value = 0;
    ArrayList<T> selected = null;

    for (ArrayList<T> v : variants)
    {
        double x = 0;

        for (T p : v)
            x += valueFunction.apply(p);

        if (x > value)
        {
            value = x;
            selected = v;
        }
    }

    return selected;
}

private ArrayList<ArrayList<T>> findVariants(ArrayList<T> list)
{
    ArrayList<ArrayList<T>> ret = new ArrayList<>();
    Conflict c = findConflicts(list);

    if (c == null)
        ret.add(list);

    else
    {
        ret.addAll(findVariants(c.v1));
        ret.addAll(findVariants(c.v2));
    }

    return ret;
}

private Conflict findConflicts(ArrayList<T> list)
{
    // Sort conflicts by the number of items remaining in the first list
    TreeSet<Conflict> ret = new TreeSet<>((c1, c2) -> Integer.compare(c1.v1.size(), c2.v1.size()));

    for (T p : list)
    {
        ArrayList<T> conflicting = new ArrayList<>();

        for (T p2 : list)
            if (p != p2 && p.isConflicting(p2))
                conflicting.add(p2);

        // If conflicts are found create subsets by
        // - v1: removing p 
        // - v2: removing all objects offended by p
        if (!conflicting.isEmpty())
        {
            Conflict c = new Conflict(p);

            c.v1.addAll(list);
            c.v1.remove(p);

            c.v2.addAll(list);
            c.v2.removeAll(conflicting);

            ret.add(c);
        }
    }

    // Return only the conflict with the highest number of elements in v1 remaining.
    // The algorithm seems to behave in such a way that it is sufficient to only  
    // descend into this one conflict. As the root list contains all items and we use
    // the remainder of objects there should be no way to miss an item.
    return ret.isEmpty() ? null 
                         : ret.last();
}



private class Conflict
{
    /** contains all items from the superset minus the offending object */
    private final ArrayList<T>  v1  = new ArrayList<>();

    /** contains all items from the superset minus all offended objects */
    private final ArrayList<T>  v2  = new ArrayList<>();

    // Not used right now but useful for debugging
    private final T             offender;


    private Conflict(T offender)
    {
        this.offender = offender;
    }
}
}

使用以下设置的变体进行测试：

public static void main(String[] args)
{
    BenefitSelector<Scavenger> sel = new BenefitSelector<>();

    ArrayList<Scavenger> proposals = new ArrayList<>();
    proposals.add(new Scavenger("P1",   new Resource[] {Resource.B},                            0.5));
    proposals.add(new Scavenger("P2",   new Resource[] {Resource.A, Resource.B, Resource.C},    4));
    proposals.add(new Scavenger("P3",   new Resource[] {Resource.C},                            2));
    proposals.add(new Scavenger("P4",   new Resource[] {Resource.A, Resource.B},                1.5));
    proposals.add(new Scavenger("P5",   new Resource[] {Resource.A},                            2));
    proposals.add(new Scavenger("P6",   new Resource[] {Resource.C, Resource.D},                3));
    proposals.add(new Scavenger("P7",   new Resource[] {Resource.D},                            1));

    ArrayList<Scavenger> result = sel.select(proposals, (p) -> p.value);
    System.out.println(result);
}

private static class Scavenger implements IConflicting
{
    private final String        name;
    private final Resource[]    resources;
    private final double        value;


    private Scavenger(String name, Resource[] resources, double value)
    {
        this.name = name;
        this.resources = resources;
        this.value = value;
    }



    @Override
    public boolean isConflicting(IConflicting other)
    {
        return !Collections.disjoint(Arrays.asList(resources), Arrays.asList(((Scavenger) other).resources));
    }

    @Override
    public String toString()
    {
        return name;
    }
}

这导致 [P1(B), P5(A), P6(CD)] 的组合值为 5.5，高于任何其他组合（例如 [P2(ABC), P7(D) ]=5).由于变体在 selected 之前不会丢失，因此处理相同的变体也很容易。

查找具有非冲突类别的项目子集

Finding subsets of items with non-conflicting categories

algorithm

set

combinatorics