如何在加权间隔调度中更喜欢较长的间隔



加权间隔调度有一个相当容易实现的快速解决方案。以下是python中的一些代码:

# A class to store a Job
class Job:
def __init__(self, start, finish, profit):
self.start = start
self.finish = finish
self.profit = profit


# Function to perform a binary search on the given jobs, which are sorted
# by finish time. The function returns the index of the last job, which
# doesn't conflict with the given job, i.e., whose finish time is
# less than or equal to the given job's start time.
def findLastNonConflictingJob(jobs, n):

# search space
(low, high) = (0, n)

# iterate till the search space is exhausted
while low <= high:
mid = (low + high) // 2
if jobs[mid].finish <= jobs[n].start:
if jobs[mid + 1].finish <= jobs[n].start:
low = mid + 1
else:
return mid
else:
high = mid - 1

# return the negative index if no non-conflicting job is found
return -1


# Function to print the non-overlapping jobs involved in maximum profit
# using dynamic programming
def findMaxProfitJobs(jobs):

# sort jobs in increasing order of their finish times
jobs.sort(key=lambda x: x.finish)
print([(jobs[i].start, jobs[i].finish) for i in range(len(jobs))])

# get the number of jobs
n = len(jobs)

# `maxProfit[i]` stores the maximum profit possible for the first `i` jobs, and
# `tasks[i]` stores the index of jobs involved in the maximum profit
maxProfit = [None] * n
tasks = [[] for _ in range(n)]

# initialize `maxProfit[0]` and `tasks[0]` with the first job
maxProfit[0] = jobs[0].profit
tasks[0].append(0)

# fill `tasks[]` and `maxProfit[]` in a bottom-up manner
for i in range(1, n):

# find the index of the last non-conflicting job with the current job
index = findLastNonConflictingJob(jobs, i)

# include the current job with its non-conflicting jobs
currentProfit = jobs[i].profit
if index != -1:
currentProfit += maxProfit[index]

# if including the current job leads to the maximum profit so far
if maxProfit[i - 1] <= currentProfit:
maxProfit[i] = currentProfit

if index != -1:
tasks[i] = tasks[index]
tasks[i].append(i)

# excluding the current job leads to the maximum profit so far
else:
tasks[i] = tasks[i - 1][:]
maxProfit[i] = maxProfit[i - 1]

# `maxProfit[n-1]` stores the maximum profit
print("The maximum profit is", maxProfit[n - 1])

# `tasks[n-1]` stores the index of jobs involved in the maximum profit
print("The jobs involved in the maximum profit are", end=' ')
for i in tasks[n - 1]:
print((jobs[i].start, jobs[i].finish, jobs[i].profit), end=' ')


if __name__ == '__main__':
jobs = [
Job(0, 3, 4), Job(0, 7, 8), Job(4, 7, 4)
]

findMaxProfitJobs(jobs)

代码输出:

The jobs involved in the maximum profit are (0, 3, 4) (4, 7, 4) 

在这种情况下,两个区间(0,3(和(4,7(的两个权重总和为与区间(0,7(的权重相同的值。当这种情况发生时,我希望算法返回一个较长的间隔,但此代码返回两个较短的间隔。

如何修改代码/算法以选择更长的间隔作为平局决胜局?

适当的标准应该是较低的间隔数,而不是较长的间隔。因此,我们使用两个标准进行求解:

  1. 提供最大重量(利润(
  2. 使用最小作业数

注意:当前代码的一个问题是使用浅拷贝而不是深度拷贝,即

tasks[i] = tasks[i - 1][:]  # Shallow copy
tasks[i] = deepcopy(tasks[i-1]  # Deep copy

在更复杂的情况下,在提供正确利润的同时使用浅拷贝会提供不正确的工作。

代码

from copy import deepcopy
# A class to store a Job
class Job:
def __init__(self, start, finish, profit):
self.start = start
self.finish = finish
self.profit = profit


# Function to perform a binary search on the given jobs, which are sorted
# by finish time. The function returns the index of the last job, which
# doesn't conflict with the given job, i.e., whose finish time is
# less than or equal to the given job's start time.
def findLastNonConflictingJob(jobs, n):

# search space
(low, high) = (0, n)

# iterate till the search space is exhausted
while low <= high:
mid = (low + high) // 2
if jobs[mid].finish <= jobs[n].start:
if jobs[mid + 1].finish <= jobs[n].start:
low = mid + 1
else:
return mid
else:
high = mid - 1

# return the negative index if no non-conflicting job is found
return -1


# Function to print the non-overlapping jobs involved in maximum profit
# using dynamic programming
def findMaxProfitJobs(jobs):

# sort jobs in increasing order of their finish times
jobs.sort(key=lambda x: x.finish)
print([(jobs[i].start, jobs[i].finish) for i in range(len(jobs))])

# get the number of jobs
n = len(jobs)

# `maxProfit[i]` is a tuple containing the maximum profit possible for the 
# first `i` jobs and the negative of the number of jobs to achieve 
# this profit. We use negative intervals since when looking for max, 
# the number of intervals will be minimized as a tie-breaker on profit
# `tasks[i]` stores the index of jobs involved in the maximum profit
maxProfit = [None] * n
tasks = [[] for _ in range(n)]

# initialize `maxProfit[0]` and `tasks[0]` with the first job
maxProfit[0] = (jobs[0].profit, -1)
tasks[0].append(0)

# fill `tasks[]` and `maxProfit[]` in a bottom-up manner
for i in range(1, n):

# find the index of the last non-conflicting job with the current job
index = findLastNonConflictingJob(jobs, i)

# include the current job with its non-conflicting jobs
currentProfit = (jobs[i].profit, -1)   # (profit, negative of number of jobs)
if index != -1:
# current tuple of profit and negative of number of intervals
currentProfit = (currentProfit[0] + maxProfit[index][0], 
currentProfit[1] + maxProfit[index][1])


# if including the current job leads to the maximum profit so far
if maxProfit[i - 1] <= currentProfit:
# comparison of tuple based upon profit and number of jobs
maxProfit[i] = currentProfit

if index != -1:
tasks[i] = deepcopy(tasks[index])
tasks[i].append(i)

# excluding the current job leads to the maximum profit so far
else:
tasks[i] = deepcopy(tasks[i - 1])
maxProfit[i] = maxProfit[i - 1]

# `maxProfit[n-1]` stores the maximum profit
print("The maximum profit is", maxProfit[n - 1])

# `tasks[n-1]` stores the index of jobs involved in the maximum profit
print("The jobs involved in the maximum profit are", end=' ')

for i in tasks[n - 1]:
print((jobs[i].start, jobs[i].finish, jobs[i].profit), end=' ')
print()


if __name__ == '__main__':
# Test 1
print('Test 1')
jobs = [
Job(0, 3, 4), Job(0, 7, 8), Job(4, 7, 4)
]

findMaxProfitJobs(jobs)

# Test 2
print('nTest 2')
jobs = [
Job(2, 2, 50), Job(3, 5, 20), Job(6, 19, 100), Job(2, 100, 200)
]

findMaxProfitJobs(jobs)

输出

Test 1
[(0, 3), (0, 7), (4, 7)]
The maximum profit is (8, -1)
Tasks [[0], [1], [1]]
The jobs involved in the maximum profit are (0, 7, 8) 
Test 2
[(2, 2), (3, 5), (6, 19), (2, 100)]
The maximum profit is (250, -2)
Tasks [[0], [0, 1], [0, 1, 2], [0, 3]]
The jobs involved in the maximum profit are (2, 2, 50) (2, 100, 200) 

相关内容

  • 没有找到相关文章

最新更新