troysps 2020-08-18
钓鱼问题:有n(2<=n<=25) 个湖从左到右一字排开。从第i个湖走到第i+1个湖要耗时t[i]个时间片(每个时间片 5 分钟)。John有 h(1<=h<=16) 个小时可以用在这些湖钓鱼(包括湖间行走时间)。在每个湖待的时间必须是整数个时间片或 0 。就算钓不着鱼了,也可以在湖边呆着。对于湖i John在那里的第一个时间片可以钓到鱼f[i]条,且后续的每个时间片,能钓到的鱼数量都比上一个时间片少d[i]。如果预计在一段时间内捕获的鱼的数量小于或等于di,则在下一个时间段内湖中将不再有鱼。为了简化规划,约翰假定没有其他人会在湖边钓鱼,以影响他期望捕获的鱼的数量。注意John只能 从第一个湖出发,从左往右走,不能回头 。最后John要停在哪里都可以。问John最多能钓多少条鱼。还要输出钓鱼方案,即在每个湖各呆多长时间。如果有多种方案,则优先选择在第一个湖呆时间最长的。如果还有多种,则优先选择在第二个湖呆的时间最长的……输入:您将在输入中获得一些案例。每种情况都以包含n的行开始。这后面跟着一个包含h的行。接下来,有一行n个整数指定fi(1<=i<= n),然后是一行n个整数di(1<=i<=n),最后是一行n-1个整数ti 1<=i<=n-1)。输入由n=0的情况终止。数据输出:对于每个测试案例,打印每个湖泊花费的分钟数(以逗号分隔),以实现预计捕获的鱼数量最大的计划(即使超过80个字符,您应该在一行上打印整个计划)。接下来是一条包含预期鱼类数量的线。如果存在多个计划,则选择在湖1尽可能长时间花费的计划,即使预计在某些间隔内不会捕获鱼。如果还有一条路径,选择在湖边2尽可能长的那一条,等等。在个案之间插入一个空行。输入:2 --几个湖1 --1个小时10 1 --第1个5分钟的时间片,第1个湖可以钓10条鱼,第2个湖可以钓1条鱼2 5 --每个时间片后,每个湖减少的鱼的数量2 --从1湖走的2湖需要花费的时间片4410 15 20 170 3 4 31 2 34410 15 50 300 3 4 31 2 30输出:45, 5Number of fish expected: 31240, 0, 0, 0Number of fish expected: 480115, 10, 50, 35Number of fish expected: 724难点:走路时间可多可少,不知道到底该花多长时间纯钓鱼才最好(可能有好湖在很右边)。解决:枚举最终停下来的湖,将方案分成n类。每类方案的走路时间就是确定的。在每类方案里找最优解,然后再优中选优。贪心:在确定停下来的湖是x的情况下,假定纯钓鱼时间是k个时间片。用三元组(F,i,j) (i<=x,1<=j<= k)表示湖i的第j个时间片能够钓的鱼的数目是F将所有的(F,i,j 共x*k个)按F值从大到小排序,选前k个,就构成了最佳钓鱼方案本题思路就是枚举最终停下来的湖,这样就能算出纯钓鱼的时间片个数 K 。然后用一个三元组(F,i,j)表示第i个湖的第j个时间片所能钓到鱼的数量为F。然后按照钓鱼的数量从大到小排序,取前K个即是问题的答案!思路:采用贪心策略:假设他从1湖泊走到x湖泊,这还剩下Y个时间,(单位时间为5分钟)。然后再用剩下的时间去钓1-x的湖泊的鱼。每次都选择最多鱼的湖泊钓。由于每个湖都必须经过,且只经过一次,所以john花在路中的总时间是确定的。在这个条件下,可以想成john学会了“瞬间移动”,即:他可以在任何时间,移动到任何他想去的湖,而移动的过程无需时间。于是,john只需在每个5分钟的开始“瞬间移动”到当前5分钟中能钓到最多的鱼的湖中,且只钓5分钟的鱼。这样可以保证john钓到尽可能多的鱼。只要枚举john的行程是从第一个湖到第k个湖(1<=k<=n),比较出最大的钓鱼数,就是题目所求的最佳方案。贪心算法:每次选择一个局部最优策略进行实施,而不去考虑对今后的影响。采用贪心策略,每次选择鱼最多的湖钓一次鱼,可以认为约翰能从一个湖“瞬间转移”到另一个湖,即在任意一个时刻都可以从湖1到湖pos中任选一个钓一次鱼。直接用贪心策略,哪个湖现在每单位时间能钓的鱼数目最多,则在哪个湖钓。我们假设只在前i个湖钓鱼,那么我们走路的时间是不是可以求出来了。那么求出这个时间以后,用总时间减去走路时间就得到了能用与钓鱼的时间,在减去走路时间后,我们就可以在前i个湖之间直接“瞬移”既然可以瞬移的话,我们每次选择现在单位时间能钓的最多的鱼的湖,在这个湖钓一个单位时间,鱼总数增加,这个湖单位时间能掉的鱼减少,然后我们再次选择单位时间可以钓最多的湖,。。。(循环)。。。。。https://blog.csdn.net/an94460061/article/details/89424135https://blog.csdn.net/TYF_wind/article/details/86361484python代码实现:
def main(): # n个湖 fi, di = [], [] n = int(input()) h = int(input()) # 转换为分钟/5,得到总共呆多久的时间片 p = h*60/5 fi = list(map(int, input().split())) # 从1开始计算,方便理解 fi.insert(0, 0) di = list(map(int, input().split())) di.insert(0, 0) ti = list(map(int, input().split())) # 遍历假设每个湖是终点,在所有时间片都用完的情况下,可以钓到鱼的数量放入一个list # 索引从1开始,方便后续理解 # 假设第一个湖是终点,得到一个最大值,然后再假设第2个湖是终点,也得到一个最大值 # 依次遍历所有的湖做终点,最后找出在哪个湖最大值,既是最好的方案 fist_list = [] # 最大可以钓鱼数量 max_fish_num = 0 for i in range(1, n+1): # 第一个湖第1个时间片所能钓到鱼的数量 fish_num = fi[i] # 实际可以钓鱼用的时间片 = 总共的时间片-行走的时间片 reality = 0 # 第一次原地不动,所以不需要减去移动时间 if i == 1: reality = int(p) else: reality = int(p - sum(ti[0:i-1])) for j in range(1, reality+1): fist_list.append([fish_num, i]) # 捕获的鱼的数量小于或等于di,则在下一个时间段内湖中将不再有鱼 if fish_num <= di[i]: fish_num = 0 else: fish_num = fish_num - di[i] # 计算每次的最大可以钓鱼数量 fist_list = sorted(fist_list, key=lambda x: x[0], reverse=True) """ 0-表示某个时间片所能钓鱼的数量,1-表示哪个湖 [[10, 1], [8, 1],[6, 1],[4, 1],[2, 1], [0, 1],[0, 1],[0, 1],[0, 1],[0, 1], [1, 2],[0, 2],[0, 2],[0, 2],[0, 2], [0, 2],[0, 2],[0, 2],[0, 2],[0, 2]] [[10, 1], [8, 1], [6, 1], [4, 1], [2, 1], [1, 2], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 2], [0, 2], [0, 2], [0, 2], [0, 2], [0, 2], [0, 2], [0, 2], [0, 2] ] """ total_fish_num = 0 # 计算终点是i湖可以钓到鱼的最大值 for k in range(reality): total_fish_num += fist_list[k][0] # 如果新计算出来的值大于之前的值,说明目前的方案是最优的, # 需要更新最大值,同时要更新每个湖停留时间的方案 if total_fish_num > max_fish_num: max_fish_num = total_fish_num lake_list = [0] * (n + 1) for c in range(reality): lake_list[fist_list[c][1]] += 1 # lake_list索引1位置,代表1湖 for j in range(1, n+1): stop_time = lake_list[j] * 5 print("%d " % stop_time, end="") print("") print("The total number of fish is:%d" % max_fish_num) return 0 if __name__ == ‘__main__‘: main()