首页 > 试题广场 >

牛牛们吃糖果

[编程题]牛牛们吃糖果
  • 热度指数：2287 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解

有个牛牛一起去朋友家吃糖果，第个牛牛一定要吃块糖果.

而朋友家一共只有块糖果，可能不会满足所有的牛牛都吃上糖果。

同时牛牛们有个约定，每一个约定为一个牛牛的编号对，表示第个和第个牛牛是好朋友，他俩要么一起都吃到糖果，要么一起都不吃。

保证每个牛牛最多只出现在一个编号对中。

您可以安排让一些牛牛吃糖果，一些牛牛不吃。

要求使能吃上糖果的牛牛数量最多（吃掉的糖果总量要小于等于），并要满足不违反牛牛们的个约定。


输入描述:
第一行个正整数 ，
第二行个正整数 ,
第三行个整数
接下来行，每行两个正整数 ，表示第个牛牛与第个牛牛有约定。


输出描述:
一行一个数字表示最多能吃上糖果的牛牛个数
示例1

输入

3 10
5 1 5
1
1 3

输出

2
算法知识视频讲解
开通博客
头像 CUG23届硕士毕业生
发表于 2022-04-11 21:22:44
经典0-1背包问题 题目简述： n个牛牛吃m个糖果，每个牛牛吃ai个，k对牛牛绑定必须一起吃或不吃，每个牛牛只会出现在一对绑定中（不会重婚） 求能够吃到糖果的牛牛的最大数量。 很显然，我们把配对了的两只牛牛看作一个权值为2的物品，所需容积为二者之和；把单身的牛牛看作权值为1的物品，所需容积就是其本身 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 wolverine12138
发表于 2022-01-06 20:37:06
01背包问题 动态规划中的核心在构建动态规划的矩阵和更新的方法。 1、矩阵行（i）:表示仅考虑[0, 1, ..., i]元素。 2、矩阵列（j）:表示最大容量为j。 此时dp[i][j]即表示相应的奖励，在选择i元素后，可选元素和最大容量都收缩。更新策略是外层累加i，内层增加最大容量j。可以采用滚 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 不想看论文
发表于 2022-03-25 10:25:22
0/1背包问题——java版 将糖果的数量看作背包的容量，将牛牛看作物品，牛牛需要糖果的数量看作物品的重量，牛牛的数量看作物品的价值。 至于约定，只需要将有约定的两只牛打包成一个物品，这个物品的重量为两只牛需要的糖果数量和，物品的价值为2（两只牛）。 代码如下： public class Main{ 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 阿里巴巴 测试工程师 PHP工程师 安全工程师 游戏研发工程师 2021 数据库工程师 信息技术岗 区块链 测试开发工程师 大数据开发工程师 数据分析师 Java工程师
上传者：小小
难度：
12条回答 6962浏览

热门推荐

通过挑战的用户

相关试题

牛牛们吃糖果

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号