給出一個數字串列A，目標是找到您可以對每個專案進行的最小可能劃分數，以獲得x其中的一個x <= sum(A)/2。
例如，
- 如果
A = [10,10]您可以除以A[0]2，您也可以除以A[1]2 以獲得串列總和的一半。因此，最小可能的分割數等于2， - 如果
A = [200, 25,25,25]您可以除以A[0]/2^2，那么x =[50,25,25,25]哪個總和125 <= 275最小可能的除法數等于3。
我嘗試了以下方式，它作業得很好，但是當我輸入這樣的huage串列時，get_f([200,25,25,25,490,99999, 2000, 43002])我得到了超時錯誤。
import itertools
def get_f(A):
A = sorted(A)[::-1]
Goal = sum(A)/2
filters = []
x = itertools.product(range(len(A)), repeat=len(A))
for i in x:
i = list(i)
C = A.copy()
x = 0
for Index in i:
C[Index]/=2
x =1
if sum(C) <= Goal and x not in filters:
filters.append(x)
return sorted(filters)[0]
uj5u.com熱心網友回復：
當前接受的解決方案是不正確的——例如，它永遠不會回傳大于輸入串列長度的數字，無論這些數字有多大。
解決此問題的最佳方法是使用優先級佇列 - 允許您避免max()一遍又一遍地重新計算（如另一個答案中所做的那樣）。
代碼：
from heapq import heapify, heappop, heappush
from itertools import count
from math import isclose
def solve(nums):
heap = [-x for x in nums]
heapify(heap)
total = sum(nums)
target = total / 2
for divs in count():
if total < target or isclose(total, target):
return divs
delta = heappop(heap) / 2
total = delta
heappush(heap, delta)
演示：
>>> print(solve([200, 25, 25, 25]))
2
>>> print(solve([200, 25, 25, 25, 0]))
2
>>> print(solve([100, 25, 100, 25]))
3
注意：問題陳述中的原始示例是錯誤的-您可以將 200 除以 2 兩次，并且總和[50, 25, 25, 25] = 125小于原始總和275，因此答案為2，而不是3。
uj5u.com熱心網友回復：
這是我的代碼版本。它在測驗中作業得很好。看看這個。
def get_f(A):
"""
A: list of numbers
return: int
"""
x = sum(A) // 2
if x == 0:
return 0
count = 0
for i in A:
if i <= x:
count = 1
return count
print(get_f([10,10]))
print(get_f([200, 25,25,25]))
print(get_f([10,10,10]))
print(get_f([10,10,10,10]))
print(get_f([200,25,25,25,490,99999, 2000, 43002]))
希望這就是你要找的
uj5u.com熱心網友回復：
def get_f(xs):
goal = sum(xs) / 2
f = 0
while sum(xs) > goal:
i = xs.index(max(xs))
xs[i] /= 2
f = 1
return f
如果可以改變輸入串列，這應該可以作業。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/422811.html
標籤：
上一篇：找到最大重復子樹