编程题 你是一名医院的护士，粗心的你拿到药片后并没有进行分组，只记得要平均成两份，然而当你想起这件事的时候，病人的药片已经被分成了好几瓶。瓶字中的药片无法取出。鲜有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

相关问题

c++编程题 你是一名医院的护士，粗心的你拿到药片后并没有进行分组，只记得要平均成两份，然而当你想起这件事的时候，病人的药片已经被分成了好几瓶。瓶字中的药片无法取出。鲜有n个药瓶，第二行n个数字代表每个药瓶中药片的数量，现在你想知道，是否可以将药片通过将药瓶组合的方式平均成两份（不允许拆分每瓶药片） 输入描述：首先输入一个数字n，代表药瓶的数量，第二行输入n个数字，代表每个瓶子中药片的数量nums

思路：首先计算总药片数，如果总药片数是奇数，那么无法平均成两份，直接返回false；如果总药片数是偶数，再判断是否存在某种药瓶，它的药片数量正好等于总药片数的一半，那么这瓶药片就可以单独分成一份，不参与其他药瓶的组合，其他药瓶组合成的药片数也应该正好是总药片数的一半，否则无法平均分成两份，返回false。

时间复杂度：O(n)

Python代码：

python编程题 你是一名医院的护士，粗心的你拿到药片后并没有进行分组，只记得要平均成两份，然而当你想起这件事的时候，病人的药片已经被分成了好几瓶。瓶字中的药片无法取出。鲜有n个药瓶，第二行n个数字代表每个药瓶中药片的数量，现在你想知道，是否可以将药片通过将药瓶组合的方式平均成两份（不允许拆分每瓶药片） 输入描述：首先输入一个数字n，代表药瓶的数量，第二行输入n个数字，代表每个瓶子中药片的数量nums

输出描述：如果能平均分成两份，输出"YES"，否则输出"NO"

示例：

输入：
4
4 4 4 4

输出：
YES

输入：
4
4 4 3 3

输出：
NO

【注意】：样例仅供解释说明，非程序输出结果。