加权间隔调度与两个可用的“工人”

概述我正在尝试编写一段代码,该代码采用一组加权间隔,并在最大化权重的两个“工人”之间进行最佳分配.输入的示例如下. 91 2 11 3 32 4 13 5 14 6 25 7 16 8 27 9 18 10 2 “9”是间隔量,列定义为 s f vs=start timef=finish timev=weight 到目前为止,我已经使用二进制搜索来确定“p”值,该值是最右边的 我正在尝试编写一段代码,该代码采用一组加权间隔,并在最大化权重的两个“工人”之间进行最佳分配.输入的示例如下.

91 2 11 3 32 4 13 5 14 6 25 7 16 8 27 9 18 10 2

“9”是间隔量,列定义为

s f vs=start timef=finish timev=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 binarySearchLastfor (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 queuefor (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",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 26 8 24 6 22 4 11 2 1room 2:8 10 26 8 24 6 22 4 11 2 1

当“正确”输出应如下所示：

room 1:8 10 26 8 24 6 22 4 11 2 1room 2:7 9 15 7 13 5 11 3 3

任何见解都将受到高度赞赏.

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

解决方法 首先,关于要求……

当你说你想“在最大化权重的两个工人之间最佳地分配任务”时,我假设你想要给工人分配任务,以便(a)没有工人根据开始 – 结束间隔重叠任务,但是(b)最多实际上,按重量分配的工作可以分配给工人.如果任务重叠太多,则可能无法将所有任务分配给两个工作人员,因为重叠. (使用您的测试数据,可以分配所有任务.)

如果是这样,这是knapsack problem的变种,但有两个背包.这个问题被称为“NP难”,实际上意味着它需要比你编码更复杂的解决方案 – 毫无疑问是使用递归编程的东西.然而,有更简单的算法可以产生足够好但通常不是最佳的答案.

第二,关于你的解决方案……

代码的中心部分需要注意.你有：

M[0]=0;M2[0]=0;//checks to see if the resulting weight is bigger in a certain queuefor (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 queuefor (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中是不好的.您的代码不适用于load1和load2中权重[i]都很好的情况,或者两者都不好的情况.此外,对于每个i,代码分配给load1 [i]或load2 [i],但不是两者,因此在循环结束时,一半的数组值是未定义的.

因此,您总是转到使用零填充load1的默认ELSE.在循环结束时,load1充满零,load2未定义*(load2 [0]除外).

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

该怎么办？如果您需要保证最优算法,建议您查看背包问题.如果一个“足够好”的算法可以做,也许你可以尝试一些简单的算法(例如,将每个任务分发给第一个有能力的工人),看看它们如何与不同的测试数据集一起运行.

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

总结

以上是内存溢出为你收集整理的加权间隔调度与两个可用的“工人”全部内容，希望文章能够帮你解决加权间隔调度与两个可用的“工人”所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。