4

我正在努力对我正在处理的问题进行分类，这意味着我无法弄清楚是否有任何已建立的启发式解决方案。你认为这是什么类型的问题，你会建议我如何解决它？

我有一系列桶 A、B、C、D。每个桶都可以包含一定数量的项目。桶的总大小与人口的大小相匹配。总体中的每个项目都有 A、B、C、D 的分数。

我想将项目分类到桶中，以使匹配桶的总分最大化；即桶A中所有项目的A分数，桶B中所有项目的B分数等等。因此，即使项目的 A 分数较高，理想情况下也有可能在桶 B 中，因为可能有很多项目具有高 A 分数，而很少有高 B 分数的项目。

4

2 回答 2

2

这看起来像最小成本最大流量问题。实际上，这是最大成本，但可以通过否定权重来修改。

考虑以下网络。有一个源，s和一个汇，t。

每个项目i都由一个顶点表示u_i，边s -> u_i的容量为 1，成本为 0。

每个桶也由一个顶点表示：v_A v_B，依此类推。有一条v_A -> t容量为 A 组大小且成本为 0 的边，以及其他组的类似边。

最后，有u_i -> v_G容量为 1 且成本等于（减去将项目i放入组的分数G）的边。

请注意，该网络中的任何最大流量都对应于将项目划分为组，以便每个组具有给定的大小。

观察这个网络中最小成本最大流是一个分区，其中分区的总得分最大。

这与项目的数量和组的数量很好地扩展。此外，这很容易扩展到组的大小可以变化到某个限制的情况，但每个项目仍必须属于一个组。

于 2018-05-31T11:13:36.007 回答
0

对于足够小的尺寸，元启发式（如本地搜索）可能会很好地工作。

public class WeightedKnapsackProblem {

private int numberOfBins = 0;
private int numberOfItems = 0;

private int[][] scoreMatrix;
private int[] maxItemsPerBin;

public WeightedKnapsackProblem(int[][] score, int[] maxItemsPerBin){
    this.numberOfItems = score.length;
    this.numberOfBins = score[0].length;
    this.scoreMatrix = score;
    this.maxItemsPerBin = maxItemsPerBin;
}

public int score(int[] assignment){
    int s = 0;
    for(int i=0;i<numberOfItems;i++){
        int item = i;
        int bin = assignment[item];
        s += scoreMatrix[item][bin];
    }
    return s;
}

public int cost(int[] assignment){
    int c = 0;
    int[] tmp = new int[numberOfBins];
    for(int i=0;i<numberOfItems;i++){
        tmp[assignment[i]]++;
    }
    for(int i=0;i<numberOfBins;i++){
        if(tmp[i] > maxItemsPerBin[i])
            c++;
    }
    return c;
}

private java.util.Random RANDOM = new java.util.Random(System.currentTimeMillis());

private int[] mutate(int[] orig){
    int[] out = new int[orig.length];
    for(int i=0;i<orig.length;i++)
        out[i] = orig[i];
    out[RANDOM.nextInt(out.length)] = RANDOM.nextInt(numberOfBins);
    return out;
}

public int[] localSearch(){
    // initial assignment
    int[] a0 = new int[numberOfItems];
    for(int i=0;i<numberOfItems;i++)
        a0[i] = RANDOM.nextInt(numberOfBins);

    // max score for any item
    int max = scoreMatrix[0][0];
    for(int i=0;i<scoreMatrix.length;i++)
        for(int j=0;j<scoreMatrix[i].length;j++)
            max = java.lang.Math.max(max, scoreMatrix[i][j]);

    // local search
    int[] a1 = mutate(a0);
    int c0 = score(a0) - cost(a0) * max * max;
    int c1 = score(a1) - cost(a1) * max * max;
    for(int i=0;i<1000;i++){
        if(c1 > c0){
            a0 = a1;
            c0 = c1;
        }
        a1 = mutate(a0);
        c1 = score(a1) - cost(a1) * max;
    }

    // return
    return a0;
}

public int[] repeatedLocalSearch(int k){

    // max score for any item
    int max = scoreMatrix[0][0];
    for(int i=0;i<scoreMatrix.length;i++)
        for(int j=0;j<scoreMatrix[i].length;j++)
            max = java.lang.Math.max(max, scoreMatrix[i][j]);

    int[] a0 = localSearch();
    int c0 = score(a0) - cost(a0) * max * max;

    for(int i=0;i<k;i++){
        int[] a1 = localSearch();
        int c1 = score(a1) - cost(a1) * max * max;

        if(c1 > c0){
            c0 = c1;
            a0 = a1;
        }
    }

    return a0;
}
}

该程序本质上生成随机分配的项目到垃圾箱，并反复尝试改进该初始情况。

因为使用这种技术很容易陷入局部最优，所以重复几次是有意义的，使用不同的（随机）起始配置。

以下程序使用 WeightedKnapsackProblem 类生成可能的解决方案：

    int[][] score = {   {9,5,2,3},
                        {8,9,2,1},
                        {3,2,1,4},
                        {1,2,1,2},
                        {7,8,9,2},
                        {0,1,2,3}
                    };
    int[] maxItemsPerBin = {2,1,2,1};

    WeightedKnapsackProblem wkp = new WeightedKnapsackProblem(score, maxItemsPerBin);
    int[] assignment =  wkp.repeatedLocalSearch(10);

    System.out.println(wkp.score(assignment));
    System.out.println(wkp.cost(assignment));
    System.out.println(Arrays.toString(assignment));

这打印出来：

34
0
[0, 1, 0, 3, 2, 2]

换句话说，演示问题的最高分可以解决为 34。
放错位置的项目（将超过 bin 容量）的数量为 0。

任务是：

  • 第一个垃圾箱中的第一个项目
  • 第二个垃圾箱中的第二个项目
  • 第一个垃圾箱中的第三个项目
  • 第四个箱子中的第四个项目
  • 第三个箱子中的第五个和第六个项目
于 2018-05-31T11:48:35.030 回答