【求助】ONT20改牛牛的果实收集

原题：

小动物牛牛生活在一个美丽的森林中，森林中有一排排的果树，每棵果树上都有不同数量的果实。每天，牛牛都会从森林中的某棵果树开始，然后按照固定的顺序收集果实，每次只能收集一棵树上的所有果实，然后移动到下一棵树。但是，牛牛的收集篮子有限，每天只能收集最多M个果实。
现在，给出每棵树上果实的数量，以及牛牛每天能收集的果实数量M，你需要找到牛牛每天能收集到的最大果实数量。
输入：[3, 1, 4, 2, 8],7
返回值：7

现改动条件，只要求按照顺序获取，不需要连续，问能够获取到的最大果实数量。

尝试了用动态规划去做，结果发现局部最优解不是全局最优解，想要知道这种情况下改如何解？

感谢大佬的指导，弄清楚了转移过程

#悬赏#

全部评论

推荐最新楼层

huang骑着蜗牛狂奔

阿里云_java开发(实习员工)

如果不是连续获取的话，不就是一个背包问题吗不就是动态规划吗

1 回复分享

发布于 06-06 10:24 四川

10-01 09:40

深圳大学 golang

小米云原生golang一面（30分钟）：

面试官可能以为我是实习，所以只问了半个多小时，还没手撕。。。了解我们这个岗位吗？然后跟我介绍了一下云计算。实习讲一下docker有使用过吗，讲一下你的理解（随便扯了点开发用到过的）Docker 容器怎么生成的，内部是怎么样的讲一下（完全不会。。。）k8s的架构（没了解过。。。）面试官看我基本不太了解这块，直接不问了哈哈哈下面全是go基础：go切片的底层切片并发安全吗？切片的扩容机制函数传切片带指针和不带指针有什么区别循环中修改切片内容，切片实际上会改变吗我觉得肯定会啊，面试官意思应该是说不会，下去让我自己跑一下看看（我寻思我下去跑了一下也确定会变啊）map中key的类型有什么限制吗为什...

点赞评论收藏

09-30 10:21

哈尔滨工业大学 Java

被逼签了，佬们来帮选offer！！！

楼主长春人，但是不恋家且不太想回家，Java选手 1.长光卫星，逼签中，单休但不怎么加班，待遇不错但是后续跳槽什么的都不方便 2.北京美团，实习转正，做业务开发，大概作息10 8:30 北京这个城市对我无正面加成 挤地铁挤得心累 3.珠海字节，面试不难，应该在扩张期，部门是基础架构，应该比美团强度大，薪资水平未知，珠海貌似有补贴和减税（要转go，但我不介意这个 4.北京滴滴，做海外的外卖，完全不清楚，信息获取比较少 最近写毕业论文中…应该没空再投其他的了

Jimobb：“单休不怎么加班”，在我眼里单休就是最大的加班了。论地点+薪资长光对于长春本地人应该是神一样的存在吧。论待遇上大概率珠海的字节国际电商最好，而且珠海消费远比北京低，即使是美团sp也会这样，但现在是长光逼签，北京还是珠海可以靠后看薪资决定一下我觉得还是看你到底是恋家-没感觉-不想在东北，这几个什么层次的情感吧。可能只有”不想在东北“这个层次值得放弃长光。

投递美团等公司10个岗位 >