改进的next_permutation算法

Question

我有以下作业：

我们有N个作品，持续时间是: t1，t2，.，tN，它的截止日期是d1，d2，…，dN。如果工程在截止日期前仍未完成，则相应地对b1、b2、.、bN进行处罚。工作应该按照什么顺序进行，惩罚才是最小的呢？

到目前为止，我已经编写了这段代码，它正在工作，但是我想通过跳过不必要的排列来改进它。例如，我知道工作顺序:1，2，3，4，5-将给我100分的惩罚，如果我改变顺序，我们可以这样说:2，1.--这立刻给了我120个点球，从这一刻起，我知道我不需要检查所有从21开始的排列，我必须略过它们。下面是代码：

int finalPenalty = -1;
bool z = true;
while(next_permutation(jobs.begin(), jobs.end(), compare) || z)
{
    int time = 0;
    int penalty = 0;
    z = false;
    for (int i = 0; i < verseNumber; i++)
    {
        if (penalty > finalPenalty && finalPenalty >= 0)
            break;
        time += jobs[i].duration;
        if (time > jobs[i].deadline)
            penalty += jobs[i].penalty;
    }
    if (finalPenalty < 0 || penalty < finalPenalty)
    {
        sortedJobs = jobs;
        finalPenalty = penalty;
    }
    if (finalPenalty == 0)
        break;
}

我想我应该在这里的某个地方这样做：

if (penalty > finalPenalty && finalPenalty >= 0)
            break;

但我不知道该怎么做。如果惩罚已经更高的话，它跳过了我这里的一个排列，但是它并没有跳过所有的东西，它仍然跳过了next_permutation。有什么想法吗？

编辑:我使用向量，我的工作结构如下所示：

    struct job
    {
        int ID;
        int duration;
        int deadline;
        int penalty;
    };

当读取文件时自动给出ID，从文件读取其余的ID (例如:ID= 1，工期= 5，截止日期= 10，惩罚= 10)

Answer 1

如果您计划使用由next_permutation提供的STL函数，那么您就无能为力了。

假设最后的k位数是多余的来检查。如果您要使用next_permutation函数，那么您可以使用的一种简单而低效的策略是调用next_permutation for k！时间(即那些最后k个元素的排列数)而不是计算它们的惩罚，因为你知道它们会更高。(k！假设没有重复。如果您有重复，您需要采取额外的措施才能计算)这将花费您的O(k!n)操作在最坏的情况下，如置换具有线性时间复杂度。

让我们考虑一下如何改进这个问题。在再次调用next_permutation之前，一种合理的策略可能是，一旦发现了低效设置，就可以按降序顺序对这些k位数进行排序，以便下一次调用能够有效地跳过不需要检查的排列的低效部分。考虑下面的例子。

假设我们的方法发现1，2，3，4，5将被判罚款100.然后，在下一步计算2 1 3 4 5时，如果我们的方法发现只有在计算2 1之后才能得到大于10 0的惩罚，那么如果可以使用排序和自定义比较机制按降序排序3 4 5，则只需跳过循环的其余部分，到达另一next_permutation调用，这将使您得到2 1 4 3 5，这是要继续的下一序列。

让我们考虑一下跳过多少成本。该方法需要对k位数进行排序并调用next_permutation，其总体时间复杂度为O(klogk + n)。这是对上一种方法的巨大改进，该方法具有O(k!n)。

有关我提议的方法的粗略实现，请参阅下面的内容，作为对现有代码的改进。我不得不使用类型auto，因为您没有为作业提供确切的类型。我还对这些k位数进行了排序，因为您没有提供比较函数，我想强调的是，我所做的是逆转升序。

int finalPenalty = -1;
bool z = true;
while(next_permutation(jobs.begin(), jobs.end(), compare) || z)
{
    int time = 0;
    int penalty = 0;
    z = false;
    auto it = jobs.begin();
    for (int i = 0; i < verseNumber; i++)
    {
        time += jobs[i].duration;
        if (time > jobs[i].deadline)
        {
            penalty += jobs[i].penalty;
            if(finalPenalty >= 0 && penalty > finalPenalty)
            {
                it++; // only the remaining jobs need to be sorted in reverse
                sort(it, jobs.end(), compare);
                reverse(it, jobs.end());
                break;
            }
        }
        it++;
    }
    if (finalPenalty < 0 || penalty < finalPenalty)
    {
        sortedJobs = jobs;
        finalPenalty = penalty;
    }
    if (finalPenalty == 0)
        break;
}