你是一名医院里的护士,粗心的你拿到药片后并没有进行分组,只记得要平均分成两份,然而当你想起这件事的时候,病人的药片已经被分成了好几瓶。瓶子中的药片无法取出。现在有n个药瓶,第二行n个数字代表每个药瓶中药片的数量,现在你想知道,是否可以将药片通过将药瓶组合的方式平均分成两份(不允许拆分每瓶药片)首先输入一个数字n,代表药瓶的数量,第二行输入n个数字,代表每个药瓶中药片的数量nums[i] 1<= nums.length <= 200 1 <= nums[i] <= 100 输出描述:true代表药片可以被均分、false代表药片不可被均分
时间: 2023-05-27 08:04:14 浏览: 45
示例1:
输入:
5
5 5 5 5 5
输出:
true
示例2:
输入:
5
5 5 5 5 6
输出:
false
提示:
药片数量总和为奇数时不可能均分。
如果药瓶中有一瓶药片数量大于所有药片数量的平均数,那么无论如何都无法平均分成两份。
相关问题
编程题 你是一名医院的护士,粗心的你拿到药片后并没有进行分组,只记得要平均成两份,然而当你想起这件事的时候,病人的药片已经被分成了好几瓶。瓶字中的药片无法取出。鲜有n个药瓶,第二行n个数字代表每个药瓶中药片的数量,现在你想知道,是否可以将药片通过将药瓶组合的方式平均成两份(不允许拆分每瓶药片)
思路:因为要平均成两份,所以所有药片数量的总和必须是偶数。问题可以转化为是否存在一个子集,使得这个子集的元素之和为所有元素之和的一半。
使用0/1背包问题的思想,对于每个药瓶,要么将其放入“重量”为总药片数量一半的背包中,要么不放入。最后判断能否正好装满这个背包即可。
代码实现如下:
def can_divide(nums):
total = sum(nums)
if total % 2 == 1:
return False
target = total // 2
dp = [False] * (target+1)
dp[0] = True
for num in nums:
for j in range(target, num-1, -1):
dp[j] = dp[j] or dp[j-num]
return dp[target]
# 测试
print(can_divide([1, 3, 4, 4])) # True
print(can_divide([1, 3, 4, 6])) # False
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![sb3](https://img-home.csdnimg.cn/images/20210720083646.png)