針對Timus 1005的Python解決方案的Possbile優化 - 平衡分區

今天我遇到了經典問題。針對Timus 1005的Python解決方案的Possbile優化 - 平衡分區

問題描述在Timus : 1005。

我知道如何用C++來解決它。但是，當我在python中嘗試它時，我得到超出時間限制。

我使用蠻力但失敗。然後我嘗試了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)

了TLE的測試4.

因此，儘管使用Python我的問題是如何通過問題的時間限制？

來源

2015-10-10 ArSorrw

如果'i！= k'有約束'w_i！= w_k'？因爲如果元素不同，問題可以通過python集來解決。 – marmeladze

@marmeladze這個問題並不能保證。 – ArSorrw

因爲Python整數可以任意大，單個整數可以被用於表示一個布爾陣列，諸如在第二溶液中的可變dp。這可以讓你用幾個按位操作代替內循環：

ans = sum(wi) 
up = ans // 2 
mask = 2 ** (up + 1) - 1 
dp = 1 
for x in wi: 
    dp |= dp << x & mask 
aw = dp.bit_length() - 1 
print(ans - 2 * aw)

來源

2015-10-12 18:47:29

這只是虛擬算法，不知道它是否返回正確的結果。實際上對於更小的範圍，我可以計算出它總是返回正確的結果，但對於更大的 - 真的不知道:)應該更好地檢查您的工作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)

其他結果（隨機20個1和9999之間的數字）檢查：他們都完成了不到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)

來源

2015-10-10 11:35:41 marmeladze

考慮一下情況：[9，9，6，6，6]。您的解決方案將獲得[9,6,6]和[9,6]。但正確的答案是[9,9]，[6,6,6]。 – ArSorrw

是的，你是對的。我錯過了重複元素的一部分。我會重寫它。 – marmeladze

針對Timus 1005的Python解決方案的Possbile優化 - 平衡分區

回答

相關問題