显示实现最大利润的步骤

Question

我正在传递一个包含数据的排序向量：

Job Details {Start Time, Finish Time, Profit}
Job 1:      {1         , 2          , 50    }
Job 2:      {3         , 5          , 20    }
Job 3:      {6         , 19         , 100   }
Job 4:      {2         , 100        , 200   }

该代码通过检查所有不重叠的路径(例如作业 1、2、3 或作业 1,4)来查找哪些作业最有利可图，并确定作业 1,4 是最佳值。我正在尝试构建一个函数，该函数显示代码如何获得最佳解决方案的路径。

例如，工作 1 --> 工作 4> 250 美元。

但是我在实施上迷失了方向。

主.cpp

// Find the latest job (in sorted array) that doesn't 
// conflict with the job[i]. If there is no compatible job, 
// then it returns -1. 
int latestNonConflict(vector<Task>someVector, int i)
{
for (int j = i - 1; j >= 0; j--)
{
if (someVector[j].getEndTime() <= someVector[i - 1].getStartTime())
{
return j;
}
}
return -1;
}
// A recursive function that returns the maximum possible 
// profit from given array of jobs.  The array of jobs must 
// be sorted according to finish time. 
int bruteForceMethod(vector<Task>someVector, int n)
{
// Base case 
if (n == 1)
{
return someVector[n - 1].getValue();
}
// Find profit when current job is inclueded 
int inclProf = someVector[n - 1].getValue();
int i = latestNonConflict(someVector, n);
if (i != -1)
cout << someVector[i].getLabel() << "-->";
inclProf += bruteForceMethod(someVector, i + 1);
// Find profit when current job is excluded 
int exclProf = bruteForceMethod(someVector, n - 1);

return max(inclProf, exclProf);
}
// The main function that returns the maximum possible 
// profit from given array of jobs 
int findMaxProfit(vector<Task>someVector, int n)
{
return bruteForceMethod(someVector, n);
}
int main()
{
cout << "The optimal profit is " << bruteForceMethod(tasksVector, 
tasksVector.size()) << endl;
return 0;
}

任务.h

#include <string>
using namespace std;
#ifndef Task_h
#define Task_h
class Task
{
public:
Task();
Task(string, int, int, int);
void setLabel(string);
string getLabel();
void setStartTime(int);
int getStartTime();
void setEndTime(int);
int getEndTime();
void setValue(int);
int getValue();
private:
string label;
int startTime;
int endTime;
int value;
};
#endif

任务.cpp

#include "Task.h"
Task::Task()
{
}
Task::Task(string inLabel, int inStartTime, int inEndTime, int inValue)
{
label = inLabel;
startTime = inStartTime;
endTime = inEndTime;
value = inValue;
}
void Task::setLabel(string inLabel)
{
label = inLabel;
}
string Task::getLabel()
{
return label;
}
void Task::setStartTime(int inStartTime)
{
startTime = inStartTime;
}
int Task::getStartTime()
{
return startTime;
}
void Task::setEndTime(int inEndTime)
{
endTime = inEndTime;
}
int Task::getEndTime()
{
return endTime;
}
void Task::setValue(int inValue)
{
value = inValue;
}
int Task::getValue()
{
return value;
}

Answer 1

您可以简单地考虑一个加权图G其中

• 节点就是作业
• 节点A链接到节点B如果A.endTime < B.startTime
• edge(A,B)的权重是B.profit(走通往B的路径意味着做工作B)

你想得到G最大权重的路径。

通常算法希望函数最小化，因此让我们取-B.profit权重。

我们总是可以引用弗洛伊德-沃歇尔算法，甚至前面提到的链接中还提供了路径重建算法。

自制

但是让我们自制，因为它似乎是一些家庭作业。

你可以用蛮力的方式(效率较低，但比弗洛伊德·沃歇尔更容易掌握)并检查所有最长的路径......

创建一个root节点，为子节点添加所有具有各自权重的作业，然后考虑递归函数：

def get_longest_path(node):
if !node.children 
return 0
best_all = {
w: weight(node, node.children[0]), 
path: [node, get_longest_path(node.children[0])]
}
for node.children as child //starting from 1
best_path_i = get_longest_path(child)
//if we found a path with lower total weight (that is, with maximal profit)
if best_path_i != 0 && best_path_i.weight < best_all.weight
best_all = {
w: weight(node, child), 
path:[node, best_path_i]
}
return best_all
get_longest_path(root)

请注意，您可以轻松记住get_longest_path(以避免对已经访问过的节点进行重新评估)，而不会造成太多负担

cache = {}
def get_longest_path(node):
if !node.children 
return 0
//node.id is jobId
if node.id in cache
return cache[node.id]
best_all = {
w: weight(node,node.children[0]), 
path: [node, get_longest_path(node.children[0])]
}
for node.children as child //starting from 1
best_path_i = get_longest_path(child)
//if we found a path with lower total weight (that is, with maximal profit)
if best_path_i != 0 && best_path_i.weight < best_all.weight
best_all = {
w: weight(node, child), 
path:[node, best_path_i]
}
cache[node.id] = best_all
return best_all
get_longest_path(root)

没有处理周期，但我想你没有逆转时间的工作

Answer 2

该算法可以非常类似于递归排列实现，例如产生ABC, ACB, BAC, BCA, CAB, CBA的字符串ABC。

这是一个简单的演示

您可以修改它以在不满足条件时"修剪"树(例如，后面的字母在字母表中低于前一个字母)，因此您会得到ABC，因为它是唯一一个每个成功字母都低于(A<B<C)的字母。

一旦你有了它，你现在就明白了如何在比较作业的startTime和endTime时递归Task和修剪......

因此，这是上述C++的实现：

#include <iostream>
#include <vector>
using namespace std;
struct Task {
// global counter tracking how many instances
static int counter;
int startTime;
int endTime;
int value;
int label;
Task(int inStartTime, int inEndTime, int inValue) {
startTime = inStartTime;
endTime = inEndTime;
value = inValue;
label = Task::counter++;
}
};
// store an index to each Task to keep track
int Task::counter = 1;
// build a search tree of all possible Task sequences
// pruning if next Task and current Task overlap
void jobSearchTree(vector<Task> jobSequence,
vector<Task> possibleJobs,
vector<vector<Task>> &possibleJobSequences) {
for (int i = 0; i < possibleJobs.size(); i++) {
vector<Task> l;
for (int j = 0; j < jobSequence.size(); j++)
{
l.push_back(jobSequence.at(j));
}
l.push_back(possibleJobs[i]);
// initial recursive call
if (!jobSequence.size()) {
vector<Task> searchJobs(possibleJobs);
searchJobs.erase(searchJobs.begin() + i);
jobSearchTree(l, searchJobs, possibleJobSequences);
}
// test if jobs occur sequentially
else if (l.at(l.size()-2).endTime <= l.at(l.size()-1).startTime)                {
// add the Task sequence
possibleJobSequences.push_back(l);
vector<Task> searchJobs(possibleJobs);
// remove this Task from the search
searchJobs.erase(searchJobs.begin() + i);
// recursive call with Task sequence as the head
// and the remaining possible jobs as the tail
jobSearchTree(l, searchJobs, possibleJobSequences);
}
}
}
vector<int> getBestJobSequence(vector<vector<Task>> possibleJobSequences) {
int maxProfit = 0;
int totalProfit = 0;
vector<Task> bestJobSequence;
for (auto jobSequence : possibleJobSequences) {
totalProfit = 0;
for (auto Task : jobSequence) {
totalProfit += Task.value;
}
if (totalProfit > maxProfit) {
maxProfit = totalProfit;
bestJobSequence = jobSequence;
}
}
vector<int> jobIds;
for (auto Task : bestJobSequence) {
jobIds.push_back(Task.label);
}
return jobIds;
}
int main()
{
Task s1(1, 2, 50);
Task s2(3, 5, 20);
Task s3(6, 19, 100);
Task s4(2, 100, 200);
vector<Task> allJobs = {s1, s3, s4};
vector<vector<Task>> possibleJobSequences;
vector<Task> currentJobSequence;
jobSearchTree(currentJobSequence, allJobs, possibleJobSequences);
vector<int> bestJobSequence = getBestJobSequence(possibleJobSequences);
for (auto job : bestJobSequence) {
cout << job << endl;
}
return 0;
}