我正在努力将我正在处理的问题归类,这意味着我还没有找到是否有任何已建立的启发式解决方案。您认为这是什么样的问题,您会推荐我如何解决它?
我有一系列的桶A、B、C、D。每个桶都可以容纳一定数量的物品。桶的总大小与人口的大小相匹配。人口中的物品每个都有A、B、C、D的得分。
我想将物品分类到桶中,使得匹配桶的总得分最大化;即所有物品在桶A中的A分数、在桶B中的B分数等等。因此,即使一个物品的A分数更高,它也可能理想地放在桶B中,因为可能有许多具有高A分数和少量高B分数的物品。
我正在努力将我正在处理的问题归类,这意味着我还没有找到是否有任何已建立的启发式解决方案。您认为这是什么样的问题,您会推荐我如何解决它?
我有一系列的桶A、B、C、D。每个桶都可以容纳一定数量的物品。桶的总大小与人口的大小相匹配。人口中的物品每个都有A、B、C、D的得分。
我想将物品分类到桶中,使得匹配桶的总得分最大化;即所有物品在桶A中的A分数、在桶B中的B分数等等。因此,即使一个物品的A分数更高,它也可能理想地放在桶B中,因为可能有许多具有高A分数和少量高B分数的物品。
s->u_i->v_G
路径缩成容量为1且带有负分数成本的s->v_G
边来消除实现中的顶点u_i
。然而,这意味着在相同的顶点对之间引入多条边。我认为最初的解释更易于理解,所以将其保留为注释。 - Gassapublic 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]