4

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

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[] 中的方式有​​关。看来这只是巧合，两个房间的输出相同。我仍然没有想出如何解决这个问题，但是我仍在寻求建议。

4

1 回答 1

1

首先，关于要求...

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

如果是这样，这是背包问题的变体，但有两个背包。众所周知，这个问题是“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，或两者都不好。此外，对于 each i，代码分配给load1[i]或分配给load2[i]两者，因此在循环结束时，一半的数组值是未定义的。

load1正因为如此，您总是会使用填充零的默认 ELSE 。在循环结束时，load1全是零，并且load2是 undefined*（除了load2[0]）。

稍后在打印循环中，所有的零都会导致第一个打印循环向后跳到prior表格中以打印您看到的结果。可能未初始化的load2数组也恰好为零，因此第二个打印循环执行相同的操作。

该怎么办？如果您需要有保证的最优算法，建议您研究背包问题。如果一个“足够好”的算法可以，也许你可以尝试一些简单的算法（例如，将每个任务分发给第一个有能力的工人），看看它们在不同的测试数据集下运行得如何。

（*技术上，因为load2是在程序中隐式声明static，它会被 C 编译器初始化为零，但你不应该依赖这个。）

于 2012-07-19T05:10:38.053 回答