贪心-钓鱼问题

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()
 

相关推荐