刷题刷出新高度,偷偷领先!偷偷领先!偷偷领先! 关注我们,悄悄成为最优秀的自己!

简答题

编程实现:

假设果园中有 N (1≤N≤100)种水果。猴子想要采摘一些水果带回家,但猴子采摘水果的总重量不能超过 W(1≤W≤1000)。

已知每种水果的最大采摘数量 Ni (1≤Ni≤100)、每种水果单个的重量 Wi (1≤Wi≤100)以及每种水果单个的维生素含量 Vi (1≤Vi≤100)。

在采摘水果的总重量不超过 w 的情况下,猴子最多可以获得多少维生素。

例如:N=3,W=5,表示有 3 种水果,旦猴子采摘水果的总重量不能超过 5。

每种水果的最大采摘数量 Ni、每种水果单个的重量 Wi 及每种水果单个的维生素含量 Vi,如下表:

猴子可按以下方式采摘,获得最多的维生素:

1)采摘第一种水果 3 个,3 个水果的重量为 3,3 个水果维生素含量为 6;

2)采摘第二种水果 1 个,1 个水果的重量为 2,1 个水果维生素含量为 4;

水果总的维生素含量最多为 10 (10=6+4)。

输入描述:

第一行输入两个正整数 N (1≤N≤100)和 W (1≤W≤1000),分别表示水果的种类数和猴子最多可采摘的水果总重量,

两个正整数之间以一个空格隔开

接下来 N 行,每行输入三个正整数 Ni (1≤Ni≤100)和 Wi(1≤Wi≤100) 及 Vi (1≤Vis100),分别表示某种水果的最大

采摘数量和某种水果单个的重量及某种水果单个的维生素含量,正整数之间以一个空格隔开

输出描述:

输出一个整数,表示在不能超过水果总重量 w 的情况下,猴子最多能获得到的维生素值


样例输入:

3 5
4 1 2
1 2 4
2 4 5

样例输出:

10

使用微信搜索喵呜刷题,轻松应对考试!

答案:

```pythonN, W = map(int, input().split())fruits = []for _ in range(N):Ni, Wi, Vi = map(int, input().split())fruits.append((Ni, Wi, Vi))vitamins = 0weight = 0for ni, wi, vi in fruits:for _ in range(min(ni, W // wi)):vitamins += viweight += wiW -= wiif weight > W:breakprint(vitamins)```

解析:

【喵呜刷题小喵解析】:

本题是一道典型的01背包问题,可以使用动态规划来解决。

首先,我们定义一个二维数组dp,其中dp[i][j]表示在前i种水果中,采摘总重量不超过j的情况下,最多能获得的维生素含量。

然后,我们遍历每一种水果,对于每一种水果,我们遍历可能的采摘数量,更新dp数组。

具体地,对于第i种水果,我们遍历采摘数量为0到Ni,对于每一个采摘数量k,我们更新dp[i][j] = max(dp[i][j], dp[i-1][j-k*Wi] + k*Vi),表示在前i种水果中,采摘总重量不超过j的情况下,最多能获得的维生素含量。

最后,我们输出dp[N][W],表示在采摘总重量不超过W的情况下,最多能获得的维生素含量。

但是,由于本题中N和W的取值范围比较小,我们可以使用一维数组优化动态规划,将dp[i][j]简化为dp[j],表示采摘总重量不超过j的情况下,最多能获得的维生素含量。

具体地,我们遍历每一种水果,对于每一种水果,我们遍历可能的采摘数量,更新dp数组。

对于第i种水果,我们遍历采摘数量为0到Ni,对于每一个采摘数量k,我们更新dp[j] = max(dp[j], dp[j-k*Wi] + k*Vi),表示采摘总重量不超过j的情况下,最多能获得的维生素含量。

最后,我们输出dp[W],表示在采摘总重量不超过W的情况下,最多能获得的维生素含量。

以上就是本题的解题思路。
创作类型:
原创

本文链接:编程实现: 假设果园中有 N (1≤N≤100)种水果。猴子想要采摘一些水果带回家,但猴子采摘水果的

版权声明:本站点所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速,微信扫码,获取考试解析、体验刷题服务,开启你的学习加速器!

分享考题
share