题目描述:
桌子上有一堆数量不超过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)