题目描述：
桌子上有一堆数量不超过20的果子，每个果子的重量都是不超过20的正整数，全部记录在列表 L 里面。小明和小红决定平分它们，但是由于他们都太自私，没有人愿意对方比自己分得的总重量更多。而果子又不能切开，所以最后他们商量好的平分方案是这样的：他们可以把某些果子扔掉，再将剩下的果子平分，请你求出在这种方案下他们每人最多可以分得的糖果重量。
例如，L = [1,2,3,4,5]，则输出：7
L = [1,3,6]，则输出：0
说明：对于样例1，他们最好的方案是把重量为 1 的果子扔掉，一人分得总重量为 7 的果子；样例2无法平分果子，因此答案是0。
注意：数据已于2017/05/03加强，原来能通过的代码不一定能够再次通过。
示例： 输入： L = [1, 2, 3, 4, 5] 输出： 7
分析: 对于这个题目，我原本以为和前面的 木棒放入4个边差不多，后来细细想想，又不太一样，这里是可以丢掉一些果子的。
使用 排列组合的方式，保留和不保留果子 进行排列。再对剩下的果子进行判断，判断能否分为两份。
假设剩下果子总重量为 w， 那么一半的话就是 half_w，
设容量为 n 的背包 装满的方法有 dp[n] 种。
那么当 dp[half_w] > 0 时，就表示至少有 1 种办法可以平均分为两份了。
于是：
- dp[0] = 1 表示背包容量为0时，有 1 种装满的办法。
- dp[half_w] = dp[half_w] + dp[half_w-a] ，a 是某一个果子的重量。
- 遍历每一个果子，然后再访问 half_w 到 a 的所有背包。
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
len_l = len(L)
sum_l = sum(L)
ans = 0
L.sort()
for i in range(2 ** len_l):
# 依次排列组合
b_i = str(bin(i))
sum_d_l = sum_l
d_L = [_ for _ in L]
for index, value in enumerate(b_i[:1:-1]):
# 如果当前二进制位是1，就去掉这个果子，丢掉。
if value == '1':
sum_d_l -= d_L[index]
d_L[index] = 0
# 为了减少下面的 遍历果子和背包的循环次数，将所有重量为0的果子都去掉了。
d_L.sort(reverse=False)
while d_L:
if not d_L[-1]:
d_L.pop()
else:
break
if sum_d_l % 2 or not sum_d_l:
continue
if sum_d_l < ans*2:
continue
target = sum_d_l//2
dp = [0] * (target+1)
dp[0] = 1
# 遍历果子和背包。
for n in d_L:
i = target
while i >= n:
dp[i] = dp[i] + dp[i-n]
i = i - 1
if dp[target] > 0:
ans = max(ans, target)
print(ans)