大佬教程收集整理的这篇文章主要介绍了加权间隔调度与两个可用的“工人”,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
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",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 []中包含哪些间隔的方式有关.似乎两个房间的输出是相同的巧合.我仍然没有想出要怎么做才能纠正这个问题,但我仍在寻找建议.
当你说你想“在最大化权重的两个工人之间最佳地分配任务”时,我假设你想要给工人分配任务,以便(a)没有工人根据开始 – 结束间隔重叠任务,但是(b)最多实际上,按重量分配的工作可以分配给工人.如果任务重叠太多,则可能无法将所有任务分配给两个工作人员,因为重叠. (使用您的测试数据,可以分配所有任务.)
如果是这样,这是knapsack problem的变种,但有两个背包.这个问题被称为“NP难”,实际上意味着它需要比你编码更复杂的解决方案 – 毫无疑问是使用递归编程的东西.然而,有更简单的算法可以产生足够好但通常不是最佳的答案.
@H_286_7@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 @R_749_10586@l 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中是不好的.您的代码不适用于load1和load2中权重[i]都很好的情况,或者两者都不好的情况.此外,对于每个i,代码分配给load1 [i]或load2 [i],但不是两者,因此在循环结束时,一半的数组值是未定义的.
因此,您总是转到使用零填充load1的默认ELSE.在循环结束时,load1充满零,load2未定义*(load2 [0]除外).
稍后在打印循环中,所有零都会导致第一个打印循环向后跳过前一个表以打印您看到的结果.有可能是未初始化的load2数组也恰好是零,所以第二个打印循环也做同样的事情.
该怎么办?如果您需要保证最优算法,建议您查看背包问题.如果一个“足够好”的算法可以做,也许你可以尝试一些简单的算法(例如,将每个任务分发给第一个有能力的工人),看看它们如何与不同的测试数据集一起运行.
以上是大佬教程为你收集整理的加权间隔调度与两个可用的“工人”全部内容,希望文章能够帮你解决加权间隔调度与两个可用的“工人”所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。