我有以下作业：
我们有N个作品，期限是：T1，T2，…，TN，最后期限是D1，D2，…，DN。如果工程在截止日期前未完成，则相应地罚款b1、b2、…、bn。这些工作应该按什么顺序进行，惩罚是最低限度的？
到目前为止，我已经编写了这段代码，它正在工作，但我想通过跳过不必要的排列来改进它。例如，我知道工作顺序如下：
1 2 3 4 5-将给我100分的惩罚，如果我改变顺序，让我们这样说：
21…..-它立刻给了我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;
但我不知道怎么做。如果惩罚已经更高，它在这里跳过一个排列，但它并没有跳过所有内容，它仍然会执行下一个排列有什么想法吗？
编辑：
我正在使用Vector，我的工作结构如下：
struct job
{
int ID;
int duration;
int deadline;
int penalty;
};从文件中读取时自动给出id，其余的从文件中读取（例如：id=1，duration=5，deadline=10，pension=10）
最佳答案
如果您打算使用STL提供的下一个排列函数，那么您就无能为力了。
假设最后k个数字是多余的。如果要使用next_置换函数，一个简单但效率低下的策略是调用k的next_置换！时间（即最后k个元素的排列数），而不是计算它们的惩罚，因为你知道它们会更高。（k！假设没有重复如果你有重复，你需要采取额外的措施，才能计算出）这将花费你o（k！n）最坏情况下的操作，如next_permutation has linear time complexity。
让我们考虑一下如何改进这一点。一个合理的策略可能是，一旦发现无效的设置，在再次调用下一个排列之前，按降序排列这些k位，以便下一个调用将有效地跳过不需要检查的排列的无效部分。考虑下面的例子。
假设我们的方法发现1 2 3 4 5有100的罚款然后，在下一步计算2 1 3 4 5时，如果我们的方法发现只有在计算2 1之后我们才得到高于100的惩罚，如果可以使用sort和您的自定义比较机制按降序对3 4 5进行排序，并跳过循环的其余部分，到达下一个排列调用，它将为您提供2 1 4 3 5下一个序列继续。
让我们考虑一下跳槽要花多少钱该方法需要对k个数字进行排序，并调用NExt*置换，它具有O（kLogk+n）的总体时间复杂度。这是一个巨大的改进，比以前的方法有o（k！N）。
请参阅下面对我提出的方法的粗略实现，作为对现有代码的改进。我不得不使用类型自动，因为你没有提供确切的类型的工作。我还对那些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;
}
关于algorithm - 改进next_permutation算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/36604531/