1

加权区间调度问题是这样的：给定一组加权区间，选择一组不重叠的区间，使总权重最大。加权区间 x 可以表示为三元组 x = (s, f, v)，其中 s=x 的开始时间，f=x 的结束时间，v=x 的权重或值 这些加权区间可以表示为三元组 (0,3,3) (1,4,2) (0,5,4) (3,6,1) (4,7,2) (3,9,5) (5,10,2 ) (8,10,1) 编写一个程序来计算加权间隔调度问题的解决方案。这是图表的图片：http: //imgur.com/vZn04xn

程序应打印出最优解的总权重值和所选区间的指数。在上述情况下，输出将类似于（此输出不正确） 最佳值：7 间隔序列：2 5 程序必须使用递归。

计算最优值的算法是： 输入：n, s1,...,sn , f1,...,fn , v1,...,vn

按完成时间对作业进行排序，使 f1 > f2 >... > fn。计算 p(1), p(2), ..., p(n) 其中 p(j) = 最大索引 i < j 使得作业 i 与 j 兼容。

for j = 1 to n
   M[j] = empty <-- solution table
M[j] = 0

M-Compute-Opt(j) {
   if (M[j] is empty)
      M[j] = max(wj + M-Compute-Opt(p(j)), M-Compute-Opt(j-1))
   return M[j]
}

我创建了一个具有 3 个整数的类 Job：开始、完成和重量。我有一个类型工作的数组，每个位置的每个不同的间隔都在大小为 8 的数组中。问题：如何计算每个作业间隔的 p？

4

2 回答 2

0

听起来像是一个可以用动态规划解决的问题。

对于从 1 到 n 的每个 i，保存您可以安排的最大权重，以及用于这些权重的最后间隔的结束日期。您只存储有趣的可能权重。例如，区间 1+4 (w=4) 没有区间 3 (w=4) 有趣，因为后者在前者之前结束并且总权重相同。

动态规划中的技巧是一项一项地移动一项，从 1 到 n。在每个步骤中，确定该步骤中可用的新数据是否会导致更好的答案、不同的可能答案或更差的答案。在进行下一步之前，只需要保存更好和不同的答案。

date    max weight  last interval
1       0           0
2       0           0
3       3           1
4       3           1
5       3 or 4      1 or 3 
6       4           3
7       4 or 5      3 or 5
8       4 or 5      3 or 5
9       5 or 8      5 or 6 
10      last step is for you, if I did not make mistakes in other rounds...
于 2013-10-28T13:49:18.533 回答
0

这可能会有所帮助......

public static int p(int index){
    for(int i=(index-1); i >=0; i--){
        if(f[i] <= s[index-1])  return i;
    }
    return -1;
}
于 2015-11-05T02:36:44.927 回答