我正在努力对我正在处理的问题进行分类，这意味着我无法弄清楚是否有任何已建立的启发式解决方案。你认为这是什么类型的问题，你会建议我如何解决它？
我有一系列桶 A、B、C、D。每个桶都可以包含一定数量的项目。桶的总大小与人口的大小相匹配。总体中的每个项目都有 A、B、C、D 的分数。
我想将项目分类到桶中，以使匹配桶的总分最大化；即桶A中所有项目的A分数，桶B中所有项目的B分数等等。因此，即使项目的 A 分数较高，理想情况下也有可能在桶 B 中，因为可能有很多项目具有高 A 分数，而很少有高 B 分数的项目。
这看起来像最小成本最大流量问题。实际上，这是最大成本，但可以通过否定权重来修改。
考虑以下网络。有一个源，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）的边。
请注意，该网络中的任何最大流量都对应于将项目划分为组，以便每个组具有给定的大小。
观察这个网络中最小成本最大流是一个分区，其中分区的总得分最大。
这与项目的数量和组的数量很好地扩展。此外，这很容易扩展到组的大小可以变化到某个限制的情况，但每个项目仍必须属于一个组。
对于足够小的尺寸，元启发式（如本地搜索）可能会很好地工作。
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。
任务是：