c - 带两个可用的加权间隔调度 "workers"

Question

我正在尝试编写一段代码，该代码采用一组加权间隔并在两个“ worker ”之间最佳地分配它们以最大化权重。输入示例如下。

9
1 2 1
1 3 3
2 4 1
3 5 1
4 6 2
5 7 1
6 8 2
7 9 1
8 10 2

“9”是间隔的数量，列定义为

s f v

s=start time
f=finish time
v=weight

到目前为止，我已经使用二进制搜索来确定“p”值，它是最右边的前一个区间，并将其存储在一个数组中。从那里，我一次一个地检查输入变量，确定最大重量以及当前间隔是否应包含在我称之为工作人员的“队列”中。

到目前为止，这是我的代码:

#include <stdio.h>
#include <stdlib.h>

#define TABSIZE (100)

int n,s[TABSIZE],f[TABSIZE],v[TABSIZE],p[TABSIZE],M[TABSIZE],M2[TABSIZE];


int binSearchLast(int *a,int n,int key)
{
// Input: int array a[] with n elements in ascending order.
//        int key to find.
// Output: Returns subscript of the last a element <= key.
//         Returns -1 if key<a[0].
// Processing: Binary search.

int low,high,mid;
low=0;
high=n-1;

// subscripts between low and high are in search range.
// size of range halves in each iteration.
// When low>high, low==high+1 and a[high]<=key and a[low]>key.
while (low<=high){
    mid=(low+high)/2;
    if (a[mid]<=key)
        low=mid+1;
    else
        high=mid-1;
}

return high;
}

main()
{
int i,j,sum=0,sum2=0;

scanf("%d",&n);
f[0]=(-999999); // For binarySearchLast
for (i=1;i<=n;i++)
    scanf("%d %d %d",&s[i],&f[i],&v[i]);
for (i=2;i<=n && f[i-1]<=f[i];i++);
    if (i<=n){
        printf("Intervals not ordered by finish time %d\n",__LINE__);
        exit(0);
    }

for (i=1;i<=n;i++)
    p[i]=binSearchLast(f,n+1,s[i]);

M[0]=0;
M2[0]=0;

//checks to see if the resulting weight is bigger in a certain queue
for (i=1;i<=n;i++){
    if(v[i]+M[p[i]]>M[i-1] && !(v[i]+M2[p[i]]>M2[i-1]))
        M[i]=v[i]+M[p[i]];
    else if(v[i]+M2[p[i]]>M2[i-1] && !(v[i]+M[p[i]]>M[i-1]))
        M2[i]=v[i]+M2[p[i]];
    else
        M[i]=M[i-1];
}


printf("\n\nroom 1:\n\n");
for (i=n;i>0; ){
    if (v[i]+M[p[i]]>=M[i-1]){
        printf("%d %d %d\n",s[i],f[i],v[i]);
        sum+=v[i];
        i=p[i];
    }
    else
        i--;
}
printf("\n\nroom 2:\n\n");
for (i=n;i>0; ){
    if (v[i]+M2[p[i]]>=M2[i-1]){
        printf("%d %d %d\n",s[i],f[i],v[i]);
        sum2+=v[i];
        i=p[i];
    }
    else
        i--;
}

printf("sum 1 is %d\n",sum);
printf("sum 2 is %d\n",sum);
}

这似乎适用于房间 1，但出于某种原因，房间 2 出现了完全相同的队列。这是我当前的输出:

room 1:

8 10 2
6 8 2
4 6 2
2 4 1
1 2 1

room 2:

8 10 2
6 8 2
4 6 2
2 4 1
1 2 1

当“正确”的输出应该是这样的:

room 1:

8 10 2
6 8 2
4 6 2
2 4 1
1 2 1

room 2:

7 9 1
5 7 1
3 5 1
1 3 3

任何见解将不胜感激。

编辑** 看着它，我认为它实际上可能与我在打印结果时确定 M[] 和 M2[] 中包含哪些间隔的方式有关。两个房间的输出相同似乎只是巧合。我仍然没有想出如何纠正这个问题，但我仍在寻求建议。

Answer 1

首先，关于要求...

当你说你想“在两个 worker 之间最优地分配任务以最大化权重”时，我假设你想将任务分配给 worker ，这样 (a) 没有 worker 有基于开始-完成间隔的重叠任务，但是 (b ) 最可能的重量工作实际分配给 worker 。如果任务重叠太多，则可能由于重叠而无法将所有任务分配给两个 worker 。 (使用您的测试数据，可以分配所有任务。)

如果是这样，这是 knapsack problem 的变体但有两个背包。这个问题被称为“NP 难”，出于实际目的，这意味着它需要比您编写的代码更复杂的解决方案——毫无疑问，这是使用递归编程的问题。然而，有一些更简单的算法可以产生足够好的答案，但通常不是最优的。

其次，关于您的解决方案...

代码的中心部分需要注意。你有:

M[0]=0;
M2[0]=0;

//checks to see if the resulting weight is bigger in a certain queue
for (i=1;i<=n;i++){
    if(v[i]+M[p[i]]>M[i-1] && !(v[i]+M2[p[i]]>M2[i-1]))
        M[i]=v[i]+M[p[i]];
    else if(v[i]+M2[p[i]]>M2[i-1] && !(v[i]+M[p[i]]>M[i-1]))
        M2[i]=v[i]+M2[p[i]];
    else
        M[i]=M[i-1];
}

我冒昧地扩展了变量名:

// Cumulative weights of tasks assigned to workers 1 and 2.
// E.g., load1[5] is total weight of tasks, selected from
// tasks 1..5, assigned to worker 1.     
load1[0] = 0;
load2[0] = 0;

// checks to see if the resulting weight is bigger in a certain queue
for (i = 1; i <= count; i++){
    if  (weight[i] + load1[prior[i]] > load1[i-1]
    && !(weight[i] + load2[prior[i]] > load2[i-1]))
        load1[i] = weight[i] + load1[prior[i]];
    else
    if  (weight[i] + load2[prior[i]] > load2[i-1]
    && !(weight[i] + load1[prior[i]] > load1[i-1]))
        load2[i] = weight[i] + load2[prior[i]];
    else
        load1[i] = load1[i-1];
}

IF 语句只满足四种可能性中的两种:weight[i] 在 load1 中很好，但在 load2 中不好，或者是在 load2 中表现良好，但在 load1 中表现不佳。您的代码不适合 weight[i] 在 load1 和 load2 中都很好，或者两者都不好的情况。此外，对于每个 i，代码分配给 load1[i] 或 load2[i] 但不会同时分配给两者，因此在循环，一半的数组值是未定义的。

因此，您总是会转到默认的 ELSE，它用零填充 load1。循环结束时，load1全为零，load2未定义*(load2[0]除外)。

稍后在打印循环中，所有的零都会导致第一个打印循环通过 prior 表向后跳转以打印您看到的结果。很可能未初始化的 load2 数组也恰好为零，所以第二个打印循环做同样的事情。

怎么办？ 如果您需要有保证的最优算法，建议您查看背包问题。如果“足够好”的算法可以，也许您可​​以尝试一些简单的算法(例如，将每项任务交给第一个有能力的 worker )，看看它们在不同的测试数据集上运行得如何。

(*从技术上讲，因为 load2 在程序中被隐式声明为 static，它会被 C 编译器初始化为零，但你不应该依赖于此。 )