首页 > 试题广场 >

牛能和牛可乐的礼物

[编程题]牛能和牛可乐的礼物
  • 热度指数：3796 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
众所周知，牛能和牛可乐经常收到小粉丝们送来的礼物，每个礼物有特定的价值，他俩想要尽可能按照自己所得价值来平均分配所有礼物。

那么问题来了，在最优的情况下，他俩手中得到的礼物价值和的最小差值是多少呢？
p.s 礼物都很珍贵，所以不可以拆开算哦

示例1

输入

[1,2,3,4]

输出

0

说明

他俩一个人拿1,4 。另一个人拿2,3
示例2

输入

[1,3,5]

输出

1

说明

他俩一个人拿1，3.另一个人拿5

备注:
单个礼物价值不超过100，礼物个数小于100，所有礼物总价值不超过10000
算法知识视频讲解
开通博客
头像 猪猪也不容易
发表于 2021-10-16 22:58:38
方法1 暴力求解 看到题目第一想法，每个礼物选或者不选有两条分支。因为我们希望尽量把礼物均分，所以要求累计价值不超出总价值的一半，否则将执行剪枝。如果出现正好均分的方案后，将flag置1，跳过后续遍历分支的步骤。当所有分支走完，找一个总价值最接近一半的方案。 很遗憾，暴力求解的方案虽然已经做了一定的 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 Miss.Zhou
发表于 2020-02-05 18:31:06
最优解：看到这种题目描述，想到要就是变形的01背包问题，只不过体积和价值都是题目中给的“礼物价值”。只要能想到这里，就可以想到把总体积的一半作为背包容量。01背包跑一下，得出的结果就是其中一个人拿到的礼物的总价值sum，然后另一个人得到的价值就是总价值减去sum，二者相减就是答案~众所周知，背包的时 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 Maokt
发表于 2021-07-30 15:08:23
算法思想一：动态规划 解题思路： 将问题转换为01背包问题，两个分组的值越接近总和一半差值越小，将总和一半看作背包的最大容量，每次放入的数字就是每次的体积，最后做差返回即可 定义dp数组，其中表示背包空间为 i 时装物品的最大价值： :背包容量 j 装不下第个礼 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 球球了给孩子一个offer吧
发表于 2021-08-02 11:51:59
题目关键信息：给定一个数组，将数组分成两个部分，使得这两部分的和的差最小 方法一：动态规划“数组”，“求最优值”显然这道题可以用动态规划解决，这是0-1背包的变形类题目，求数组两部分的和的差的最小值，假设数组的总和为，部分一的和为，部分二的和为，那么增加，就减小,减小,就增加,,因此背包的最大容量是 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 摸鱼学大师
发表于 2021-07-31 13:40:40
思路： 题目的主要信息： 给定一串数组，将数组分为两部分 要使两部分各自的和相差最小 两部分的值越接近于总和的一半，相差越小。 方法一：动态规划（01背包）具体做法：依据上面提到的性质，我们可以将这个问题看成一个01背包问题：背包容量为总和的一半，因此我们要装两部分，然后依次遍历数组，利用动态规 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 QSheng
发表于 2021-08-06 10:19:17
解题思路： 1. 01背包问题 2. 背包容量为总额的一半 class Solution: def maxPresent(self , presentVec ): """ 01 背包 """ 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 CroMarmot
发表于 2021-10-03 02:43:54
题意 给定数组presentVecpresentVecpresentVec，把数组拆分成两个子数组，使得两个子数组分别的和的差最小。 范围，数组长度n≤100n \leq 100n≤100, 所有值111到100100100之间 方法 深搜(TLE) 代码 我们可以枚举所有的选择方案，选或者不选。 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛一霸
发表于 2021-08-06 12:21:23
题目：牛能和牛可乐的礼物描述：众所周知，牛能和牛可乐经常收到小粉丝们送来的礼物，每个礼物有特定的价值，他俩想要尽可能按照自己所得价值来平均分配所有礼物。那么问题来了，在最优的情况下，他俩手中得到的礼物价值和的最小差值是多少呢？p.s 礼物都很珍贵，所以不可以拆开算哦示例1：输入：[1,2,3,4]， 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 认认真真coding
发表于 2021-08-01 13:09:10
题目描述众所周知，牛能和牛可乐经常收到小粉丝们送来的礼物，每个礼物有特定的价值，他俩想要尽可能按照自己所得价值来平均分配所有礼物。那么问题来了，在最优的情况下，他俩手中得到的礼物价值和的最小差值是多少呢？p.s 礼物都很珍贵，所以不可以拆开算哦 方法一：动态规划的方法 求解思路对于本题目的求解，我们 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 NeosKnight
发表于 2020-11-03 23:36:53
牛能和牛可乐的礼物 C++版本答案： #include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> #include< 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

动态规划 数组
难度：
12条回答 4842浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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