首页 > 试题广场 >

采药

[编程题]采药

热度指数：11502 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

辰辰是个很有潜能、天资聪颖的孩子，他的梦想是称为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到个到处都是草药的山洞里对他说： “孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。” 如果你是辰辰，你能完成这个任务吗？

输入描述:

输入的第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），T代表总共能够用来采药的时间，M代表山洞里的草药的数目。
接下来的M行每行包括两个在1到100之间（包括1和100）的的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出描述:

可能有多组测试数据，对于每组数据，
输出只包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

示例1

输入

输出

算法知识视频讲解

Python

lx的流星

while True:
    try:
        t,m=map(int,input().strip().split())
        inp=[]
        for i in range(m):
            inp.append(list(map(int,input().strip().split(' '))))
        dp=[]
        for i in range(t+1):
            dp.append([0]*(m+1))

        for i in range(t+1):
            for j in range(1,m+1):
                if inp[j-1][0]<=i:
                    dp[i][j]=max(dp[i][j-1],dp[i-inp[j-1][0]][j-1]+inp[j-1][1])
                else:
                    dp[i][j]=dp[i][j-1]
        #print(dp)
        print(dp[-1][-1])
    except:
        break

动态规划

发表于 2019-08-01 13:50:55 回复(0)

Python

TimeMac

动态规划，用一个数组values[i]表示i时间能采集到的草药价值

如果比所给时间小，从后往前到不够时间摘下该草药为止，看加入进来是否有价值增加的可能。

while True:
    try:
        t,m = list(map(int,input().split()))
        selects = []
        for i in range(m):
            selects.append(list(map(int,input().split())))
        values = [0] * (t+1)
        for i in range(m):
            if selects[i][0] <= t:
                for j in range(t,selects[i][0]-1,-1):
                    values[j] = max(values[j],values[j-selects[i][0]]+selects[i][1])
        print(values[t])
    except Exception:
        break

编辑于 2018-10-01 17:14:53 回复(0)