由于节假日如何最大限度地天假期？ [英] Given holidays and leaves how to maximize days in vacations?
问题描述
这更多的是一种算法审查： -
问题：由于节假日的整数列表，0-364之间，和叶N个可用，如何最大限度地发挥天在X中度假，在那里休假的日期范围，其中包括假期落在了数数的范围，并使用叶片的其余部分中的范围内。
我相信使用getMaxVacations以下伪code（X，0，364，N）可能工作与一些小的修正和放大器;优化，但是我正在寻找其他方法以可视化的问题，不一定要快。
available_leaves（N）= 5
节假日= [7，14，20，21，35，36]
getMaxVacation（X，开始，结束，N）{
如果X = 0返回0;
为（D：年底动工+ 1）{
对于（假：N 1）
总= bestSingleVacation（启动，D，离开）+ getMaxVacation（X-1，D，终端，N-假）;
如果MAX＆LT;总
最大=总
收益最大
}
bestSingleVacation（开始，结束，leaves_to_use）{
maxVacationSize = leaves_to_use
对于（I：启动; I＆LT;最终maxVacationSize;我++）{
对于（记者：我; J＆LT; leaves_to_use）{
如果（！holidays.contains（J））J ++; //使用许可
}
如果（maxVacationSize＆LT; JI）maxVacationSize =吉;
}
返回maxVacationSize;
}
这里的东西在Haskell使用联邦假期（1月1日至20号在列表的末尾，以便该计划将利用寒假的假期子建-sequences）。它将输出最长至最短总休假日对于x假期，利用N或假的少天 - 其中许多假期为一整天（但休假天数可能会提供给他们增加）。如果您正在寻找在X中休假的最大短的假期，它可能需要一些调整。这是一个过滤的最相结合的办法。
方法：
-
列表中的所有子序列假期。
-
从1表单中的所有组的子序列的X个
-
过滤器2，这样的日子里，在两者之间（休假天数）不超过N和返回它们通过休假天数降序排列。
样本输出对于N = 15，X = 4：
（17，[1,15]，[53]，[150]，[245]）-17天的假期13天的假使用
对于第一个假期
（14，[15,20]，[53]，[185]，[359,1]）-14天的假期，10天假期的利用
对于第一个和最后假期
项目code：
进口Control.Monad（后卫）
进口Data.List模块（sortBy，要点，相交，排序，inits，尾巴）
federalHolidays = [53,150,185,245,285,315,332,359,1,15,20]
N =假15 --days
X = 4 --number假期
差异XS =
总之$地图（\ x - ＆GT，X - 1）。尾
$ zipWith（\ AB - ＆GT;如果＆GT; B，则AB否则A + 364 - B）XS（[0] ++的init XS）
countDays假期=如果空（下降1休假）
然后1
否则，如果上次度假＆GT;头假期
那么最后的假期 - 头度假
否则最后的假期+ 365 - 头假期
maxVacations =
sortBy（\ A B - ＆GT;比较（FST B）（FST一））
$拉链（图（\ x - ＆GT;和（图countDays X））potentialVacations）
$过滤器（\Ÿ - ＆GT;和（图差异Y）＆LT; = N）potentialVacations
其中，potentialVacations =结点（图分类$解决[]）
holidaySubsequences =
过滤器（未。NULL）。 concatMap inits。麻花辫$ federalHolidays
解决结果=
如果length ==结果x
那么[结果]
做别的
H＆LT; - holidaySubsequences
守卫 （
差异H＆LT; = N
＆功放;＆安培; notElem h计算结果
＆功放;＆安培;所有空（图（相交高）的结果））
解决（H：结果）
This is more of an algorithm review :-
Problem : Given the holidays as list of integers, between 0-364, and number of leaves N available, how to maximize the number of days in X vacations, where a vacation is a date range, which encompasses holidays that falls in the range and uses leaves for the rest in the range.
I believe the following pseudo code using getMaxVacations(X, 0, 364, N) might work with some small fixes & optimizations, but I am looking for other approaches to visualize the problem, not necessarily faster.
available_leaves (N) = 5
holidays = [7, 14, 20, 21, 35, 36]
getMaxVacation (X, start, end, N) {
if X = 0 return 0;
for (d : end to start + 1) {
for (leave : N to 1)
total = bestSingleVacation(start, d, leave) + getMaxVacation(X-1, d, end, N-leave);
if max < total
max = total
return max
}
bestSingleVacation(start, end, leaves_to_use) {
maxVacationSize = leaves_to_use
for (i : start; i < end-maxVacationSize; i++) {
for (j : i ; j < leaves_to_use) {
if (!holidays.contains(j)) j++; // use the leave
}
if (maxVacationSize < j-i) maxVacationSize = j-i;
}
return maxVacationSize;
}
Here's something in Haskell using federal holidays (January 1-20 are at the end of the list so the program will utilize the winter holidays in the construction of holiday sub-sequences). It will output from longest to shortest total vacation days for X vacations, utilizing N or less days of leave - many of these vacations are one day long (but days of leave may be available to augment them). If you are looking for the maximum shortest vacation in X vacations, it may need some tweaking. This is a filtered most-combination approach.
Method:
List all the sub-sequences of holidays.
Form all groups of X number of sub-sequences from 1.
Filter 2. such that the days-in-between (days of leave) do not exceed N and return them sorted by number of vacation days descending.
Sample output for N=15, X=4:
(17,[[1,15],[53],[150],[245]]) -17 days of vacation, 13 days of leave utilized
for the first vacation
(14,[[15,20],[53],[185],[359,1]]) -14 days of vacation, 10 days of leave utilized
for the first and last vacation
Program code:
import Control.Monad(guard)
import Data.List(sortBy, nub, intersect, sort, inits, tails)
federalHolidays = [53,150,185,245,285,315,332,359,1,15,20]
n = 15 --days of leave
x = 4 --number of vacations
differences xs =
sum $ map (\x -> x - 1) . tail
$ zipWith (\a b -> if a > b then a-b else a + 364 - b) xs ([0] ++ init xs)
countDays vacation = if null (drop 1 vacation)
then 1
else if last vacation > head vacation
then last vacation - head vacation
else last vacation + 365 - head vacation
maxVacations =
sortBy (\a b -> compare (fst b) (fst a))
$ zip (map (\x -> sum (map countDays x)) potentialVacations)
$ filter (\y -> sum (map differences y) <= n) potentialVacations
where potentialVacations = nub (map sort $ solve [])
holidaySubsequences =
filter (not . null) . concatMap inits . tails $ federalHolidays
solve result =
if length result == x
then [result]
else do
h <- holidaySubsequences
guard (
differences h <= n
&& notElem h result
&& all null (map (intersect h) result))
solve (h:result)
这篇关于由于节假日如何最大限度地天假期？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
