python - Timus 1005 的 Python 解决方案的可能优化 - 平衡分区

Question

我今天遇到了经典问题。

问题描述在Timus : 1005 .

我知道如何用 C++ 解决它。 但是当我在 python 中尝试时，我得到了 Time Limit Exceeded。

我使用蛮力但失败了。然后我尝试了DP，也失败了。 这是我的解决方案:

n = int(input())
wi = list(map(int, input().split()))
ans = 1<<21
up = (1<<(n-1))-1
su = 0
for x in range(up, -1, -1):
    su = 0
    for y in range(n):
        su += wi[y] if (x & 1<<y) else -wi[y]
    ans = min(ans, abs(su))
print(ans)

它在 Test3 上获得了 TLE。

这是另一个 DP 解决方案:

n = int(input())
wi = list(map(int, input().split()))
wi.sort()
ans = sum(x for x in wi)
up = ans // 2
dp = [0] * (up + 1)
dp[0] = 1
for x in range(n):
     for y in range(up, wi[x]-1, -1):
         dp[y] |= dp[y-wi[x]]
aw = up
while not dp[aw]:
     aw -= 1
print(ans - 2 * aw)

在测试 4 中获得了 TLE。

所以我的问题是如何在使用 Python 时通过问题时限？

Answer 1

这只是虚拟算法，不知道它是否返回正确的结果。 实际上对于较小的范围，我可以计算它总是返回正确的结果，但对于更大的范围 - 真的不知道 :) 如果没问题，最好检查你的工作 C++ 代码。

 def minimizing_diff(lst):
    a  = list()
    b = list()

    for i in sorted(lst, reverse = True):
        if sum(a)>sum(b):
            b.append(i)
        else:
            a.append(i)

    return (len(a), a, len(b), b, abs(sum(a)-sum(b)))
    # I am returning the first 4 elements to debug by eye :)

这些都可以。你可以用笔和纸检查:)

0..9  => (5, [9, 6, 5, 2, 1], 5, [8, 7, 4, 3, 0], 1)
0..19 => (10, [19, 16, 15, 12, 11, 8, 7, 4, 3, 0], 10, [18, 17, 14, 13, 10, 9, 6, 5, 2, 1], 0)
0..14 => (7, [14, 11, 10, 7, 6, 3, 2], 8, [13, 12, 9, 8, 5, 4, 1, 0], 1)

其他结果(1 到 9999 之间的随机 20 个数字):所有这些都在 0.1 秒内完成。

(10, [9944, 8573, 8083, 6900, 6664, 4644, 4544, 2362, 1522, 947], 10, [9425, 8647, 8346, 7144, 6252, 6222, 3749, 1803, 1760, 126], 709)
(10, [9839, 7087, 6747, 6016, 5300, 4174, 3702, 2469, 1970, 1758], 10, [9490, 9246, 6436, 6010, 4690, 4168, 3608, 2374, 1879, 1684], 523)
(10, [9209, 8754, 8613, 6383, 6286, 5222, 4992, 3119, 2950, 147], 10, [9102, 8960, 7588, 7317, 6042, 5769, 4861, 3041, 2078, 1516], 599)
(10, [8096, 7757, 6975, 6677, 5204, 4354, 3174, 3132, 1237, 425], 10, [8033, 7765, 7140, 6089, 5511, 4385, 3482, 2877, 1253, 1139], 643)
(10, [9243, 7887, 6890, 6689, 6347, 5173, 3953, 3380, 3079, 1032], 10, [9131, 7996, 7791, 6403, 5621, 5585, 3632, 3436, 2959, 1291], 172)
(10, [9697, 8504, 7731, 7504, 6696, 4671, 4464, 3057, 1929, 1691], 10, [9384, 8540, 8319, 7233, 6252, 5549, 4275, 2154, 2023, 1794], 421)