首页 > Dima and Salad
开通博客写题解
头像 shyyhs
发表于 2021-02-03 22:07:03
思路: 一道很不错的01背包问题,比那些普及-的模板题好太多了. 首先假如你不往背包的方向想,那么我们肯定有个贼简单的想法,表示到了第个,第一个的权值为,第二个的权值为的是否存在,个人觉得内存是没问题的,分析下时间复杂度是的,显然不可取. 那么我们往背包考虑,把每个物品的体积看成,权值为.然后做一次 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 sunrise__sunrise
发表于 2021-02-04 15:57:33
题目描述 给你n个水果，每个水果有一个价值val，还有一个增加的卡路里w，要你求解的最大。如果无解输出-1。 。 Solution 我们把式子做个化简即。也就还等于。这样的前提下求解最大的，这个东西是不是在什么地方见过阿，背包的转移式里面。显然我们可以把看成是物品的体积，并且这个体积可能为负数，把看 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 MYCui_
发表于 2021-02-04 20:11:14
不错的背包题。 题解正文 首先我们最朴素的想法是什么？ 枚举每一个美味值以及每一个卡路里值，用 bool 数组存下来判断是否可达，这样子的空间复杂度是 O() 的，时间复杂度是: O()的。 首先上面的做法肯定是不行的，那么怎么办呢？ 想到要满足最后的 ，就不难想到将 作为 背包的重量，然后 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 hnust_yangyanjun
发表于 2021-02-10 23:33:14
题意：给出n个物品的ai和bi的值，求在满足所选物品ai之和除以bi之和等于k时ai之和最大为多少？ 思路：将每一个物品的ai看成价值，ai-bi*k看成体积，这样题目就变成了所选物品体积为0时价值最大为多少？给体积一开始就加上一个较大的值来解决下标为负的问题，这样就只是一个简单的01背包问题了。 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 issue是云哥的小迷×呀
发表于 2021-02-05 10:01:38
不会写...看的题解,wsfw 物品的两个属性不太好弄 假如暴力设计状态,就是定义表示在中且的状态是否存在 暴力枚举的话复杂度上天 换种思路 考虑到最后的合法方案是 也就是 不妨给所有扩大到,这样一来我们只需要关注当前选择两种属性的偏移量 如果偏移量为零,那么达到目的 因为 所以偏移量不会超过这么多 展开全文
去ta的博客 赞 (1) 回复(1) 收起
头像 hunxuewangzi
发表于 2021-02-09 20:42:37
题目链接 题目大意 给你n个物品，每个物品有两个值一个为a，一个为b 要你拿任意的物品使得 题目思路 一个显然易见的思路设为是否有 然后最后复杂度为 显然不行 所以考虑化简 把这个问题转化为每个物品重量为 价值为 转化为变为01背包 然后由于有负数，所以把背包的初始体积平移一下即可 代码 #inc 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 CoolGuang!
发表于 2021-02-04 15:05:41
题目大意： 给出两个序列，询问是否存在一种选下标的方案使得: 也就说a和b要么一起拿要么一起不拿 题目思路： 因为状态被绑定，所以可以直接考虑他们绑在一起 假设: 那么必然有： 所以说可以让b序列每个数都,之后令 也就说问题转换为了，求取的物品重量为0时，最大权值 这样就可以直接01背包了 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 あおいSakura
发表于 2021-02-12 01:05:01
Dima and Salad 题目链接：nowcoder 110246 到主站看：https://blog.csdn.net/weixin_43346722/article/details/113792591 题目大意 有一些东西，对于某个东西只能选或不选。每个东西有价值和消耗。 然后要你在保证总价 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 熠丶
发表于 2021-02-08 05:27:03
做法：01背包 思路 所以设,把a[i]看作价值，c[i]看作容量又因为c[i]有正有负，所以我们正负分开求求的是当容量为0时，价值最大。我们分别把对应的正负容量相加为0时价值相加求最大即可 代码 #include <bits/stdc++.h> using namespace s 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”