在java中使用递归的加权间隔调度

Question

加权区间调度问题是这样的:给定一组加权区间，选择一组不重叠的区间，使得总权重最大。加权间隔x可以由三元组x = (s，f，v)来表示，其中x的时间、x的时间、v=weight或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程序必须使用递归。

计算最优值的算法为: Input: n，s1，...，sn，f1，...，fn，v1，...，vn

按完成时间对作业进行排序，以便f1 > f2 >... > fn。计算p(1)，p(2)，…，p(n)，其中p( j ) =最大索引i

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个int的Job类: start、finish和weight。我有一个job类型的数组，在大小为8的数组中，每个点都有不同的间隔。问:如何计算每个作业间隔的p？

Answer 1

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

对于从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...

Answer 2

这可能会有帮助……

public static int p(int index){
    for(int i=(index-1); i >=0; i--){
        if(f[i] <= s[index-1])  return i;
    }
    return -1;
}