如何使用一组重叠最小的范围来覆盖一个范围?
How to cover a range using a set of ranges with minimal overlap?
假设有 n 项任务和一组 m 人,每个人都可以完成一定范围的任务(Ti 到 Tj) .完成每项任务的成本是k*no。完成该任务的人。如果可能的话,至少完成一次所有任务的最低成本是多少。
我觉得这是一个动态规划问题,但我无法达到最优方程。有人可以帮我找到上面的正确方程式或代码块吗?为了更好地理解,我附上了几个例子。
n:4
m:3
Range of tasks for m people: {(3,4);(1,2);(2,3)}
Answer: m1 & m2 can complete all 4 tasks so cost is 4.
Ex2:
n:4
m:2
Range of tasks for m people: {(1,3);(2,4)}
Answer: m1 & m2 are both required to complete all 4 tasks so cost is 6.
这是贪心算法 - 始终是最好的起点。
allocate all teams
IF not all sections covered
output -1
stop
mark all teams non-critical
flag_improved = true
WHILE( flag_improved == true )
flag_improved = false
find most expensive section
find most expensive non-critical team on most expensive section
IF team found that can be removed without leaving a section uncovered
remove team
flag_improved = true
ELSE
mark team critical
output cost - sum coverage of remaining teams
这是实现该算法的 C++ 应用程序的主要函数
main()
{
std::vector<cTeam> teams;
int bridge_section_count;
Input( bridge_section_count, teams);
// allocate all teams
for (int s = 0; s < bridge_section_count; s++)
Bridge.insert(std::pair(s, std::vector<cTeam>(0)));
for (auto &t : teams)
for (int s = t.myRange.first; s <= t.myRange.second; s++)
{
Bridge[s].push_back(t);
}
// check every section has at least one team allocated
if (!IsCovered())
{
std::cout << "-1\n";
exit(1);
}
// loop while improvements are being found
bool flag_improved = true;
while (flag_improved)
{
flag_improved = false;
auto most_expensive_section = find_most_expensive_section();
while (1)
{
// loop over teams allocated to most expensive section
std::vector<cTeam>::iterator most_expensive_team;
if (!find_most_expensive_non_critical_team(
most_expensive_team,
most_expensive_section))
{
break;
}
// check can team be removed without leaving section uncovered
if (testRemoval(*most_expensive_team))
{
// remove team
doRemoval(*most_expensive_team);
flag_improved = true;
break;
}
else
{
// this team is critical, it cannot be removed
most_expensive_team->myCritical = true;
}
}
}
printResult();
}
完整的应用代码在https://gist.github.com/JamesBremner/ada6210a8517671abd45e882c97d526d
假设有 n 项任务和一组 m 人,每个人都可以完成一定范围的任务(Ti 到 Tj) .完成每项任务的成本是k*no。完成该任务的人。如果可能的话,至少完成一次所有任务的最低成本是多少。 我觉得这是一个动态规划问题,但我无法达到最优方程。有人可以帮我找到上面的正确方程式或代码块吗?为了更好地理解,我附上了几个例子。
n:4
m:3
Range of tasks for m people: {(3,4);(1,2);(2,3)}
Answer: m1 & m2 can complete all 4 tasks so cost is 4.
Ex2:
n:4
m:2
Range of tasks for m people: {(1,3);(2,4)}
Answer: m1 & m2 are both required to complete all 4 tasks so cost is 6.
这是贪心算法 - 始终是最好的起点。
allocate all teams
IF not all sections covered
output -1
stop
mark all teams non-critical
flag_improved = true
WHILE( flag_improved == true )
flag_improved = false
find most expensive section
find most expensive non-critical team on most expensive section
IF team found that can be removed without leaving a section uncovered
remove team
flag_improved = true
ELSE
mark team critical
output cost - sum coverage of remaining teams
这是实现该算法的 C++ 应用程序的主要函数
main()
{
std::vector<cTeam> teams;
int bridge_section_count;
Input( bridge_section_count, teams);
// allocate all teams
for (int s = 0; s < bridge_section_count; s++)
Bridge.insert(std::pair(s, std::vector<cTeam>(0)));
for (auto &t : teams)
for (int s = t.myRange.first; s <= t.myRange.second; s++)
{
Bridge[s].push_back(t);
}
// check every section has at least one team allocated
if (!IsCovered())
{
std::cout << "-1\n";
exit(1);
}
// loop while improvements are being found
bool flag_improved = true;
while (flag_improved)
{
flag_improved = false;
auto most_expensive_section = find_most_expensive_section();
while (1)
{
// loop over teams allocated to most expensive section
std::vector<cTeam>::iterator most_expensive_team;
if (!find_most_expensive_non_critical_team(
most_expensive_team,
most_expensive_section))
{
break;
}
// check can team be removed without leaving section uncovered
if (testRemoval(*most_expensive_team))
{
// remove team
doRemoval(*most_expensive_team);
flag_improved = true;
break;
}
else
{
// this team is critical, it cannot be removed
most_expensive_team->myCritical = true;
}
}
}
printResult();
}
完整的应用代码在https://gist.github.com/JamesBremner/ada6210a8517671abd45e882c97d526d