撰寫一個函式processOrders(orders:List[int], sizes:List[int])來確定是否可以完成每個給定的訂單。此處，orders 是一個正整數串列，其中每個整數表示該訂單所要求的長度。尺寸是一個正整數串列（不一定從小到大排序），代表這家商店攜帶的單個桿長度。您的函式必須回傳布林值串列，其中第 i 個元素指示是否可以滿足第 i 個訂單。
processOrders([5, 12, 13, 20], [1, 2, 5, 10]) == [True, True, True, True]
在上面的示例中，商店出售長度為 1、2、5、10 的桿。由于商店出售 5 厘米桿，因此可以完成 5 厘米的訂單。此外，可以滿足 12 厘米的訂單，因為商店結合了 2 厘米和 10 厘米的桿。13-cm的階可以滿足，因為它是10 2 1。可以滿足 20 厘米的訂單，因為商店將兩個 10 厘米的桿焊接在一起。
我試過這樣做，但它不起作用..
def findsum(s,g):
for f in g:
for x in s:
if sum (x) == f:
return True
else:
return False
我需要做哪些改變？
編輯：任何組合都應該作業:)
uj5u.com熱心網友回復：
這個問題與代表動態規劃的一個問題非常相似，稱為硬幣找零問題。在這個問題中，我們只是嘗試驗證是否存在一種可能的組合來實作總和，而在硬幣找零問題中，我們會檢查存在多少種可能的組合。
我將首先發布這個問題的代碼，然后解釋硬幣找零問題的實作，然后解釋我們如何稍微調整它以適應這個問題。
代碼：
def findWays(order, sizes):
ways = [0] * (order 1);
ways[0] = 1;
for i in range(len(sizes)):
for j in range(len(ways)):
if (sizes[i] <= j):
ways[j] = ways[(j - sizes[i])];
if ways[len(sizes) - 1] > 0:
return True;
return False
def processOrders(orders,sizes):
fulfilled = [False] * len(orders)
for i in range(len(orders)):
fulfilled[i] = findWays(orders[i],sizes)
for i in range(len(fulfilled)):
print(fulfilled[i])
processOrders([5, 12, 13, 20], [1, 2, 5, 10])
#Output: True True True True
這個問題的關鍵是了解如何將其分解為更小的問題。首先，讓我們假設尺寸串列已排序。
讓我們從一個小例子開始：
我們想要價值 5 和價值 1、2 和 3 個硬幣的總和。
現在，讓我們創建一個陣列，列出可以對 0 到 5 之間的值求和的方法。我們將第 0 個索引設定為 1，因為只有一種方法可以求和 0。我將用索引列出它們和價值觀：
[0, 1, 2, 3, 4, 5]
[1, 0, 0, 0, 0, 0]
現在，讓我們從價值 1 的硬幣開始。從索引 1 開始，因為這是硬幣的價值，所以讓我們將該值加 1，因為僅使用價值 1 的硬幣，我們有 1 種方法可以使 1：
[0, 1, 2, 3, 4, 5]
[1, 1, 0, 0, 0, 0]
但是，如果我們有1種方法可以得到1，那么通過加1，我們可以得到2。因此，如果我們有1種方法可以得到2，那么通過加1，我們可以得到3。我們可以重復這個程序，直到達到5 ：
[0, 1, 2, 3, 4, 5]
[1, 1, 1, 1, 1, 1]
現在，讓我們從價值 2 的硬幣開始。我們從索引 2 開始。使用相同的程序，我們將 2 的值增加 1：
[0, 1, 2, 3, 4, 5]
[1, 1, 2, 1, 1, 1]
現在，用類似的思維方式：如果已經有 1 種方法可以使價值 1，那么通過添加價值 2 的硬幣，我們就有了一種獲得 3 的新方法。如果已經有 2 種方法可以獲得價值2，然后通過添加價值 2 的硬幣，我們有 2 種新的方式來獲得 4。如果已經有 2 種方式可以獲得價值 3，那么通過添加價值 2 的硬幣，我們有兩種新的方式來獲得 5：
[0, 1, 2, 3, 4, 5]
[1, 1, 2, 2, 3, 3]
現在，對于價值 3 的硬幣：將 3 的價值增加 1。如果有 1 種方法可以獲得 1，那么通過添加價值 3 的硬幣，我們有 1 種新方法可以獲得 4。如果已經有 2 種方法要獲得 2，通過添加價值 3 的硬幣，我們有兩種獲得 5 的新方法：
[0, 1, 2, 3, 4, 5]
[1, 1, 2, 3, 4, 5]
我們已經檢查了我們所有的硬幣，因此我們可以得出結論，有 5 種方法可以使用價值 1、2、3 的硬幣獲得 5 的價值。讓我們手動驗證我們的結果：
獲得 5 和的 5 種方法：
1 1 1 1 1
1 2 2
2 3
1 1 3
1 1 1 2
為了實作這個問題，每次我們檢查一個有價值的硬幣（或在這種情況下的大小）時，我們將檢查它可以制造的方法數的索引順序的值是否為1或更多。如果是，我們將退出回圈并回傳 true。
這是一個非常長的解釋，所以如果您需要更多幫助，請告訴我！
uj5u.com熱心網友回復：
這是一種方法。
import itertools
def processOrders(orders, sizes):
"""
Ref:
https://docs.python.org/3/library/itertools.html#itertools.combinations
https://stackoverflow.com/questions/70331554/how-can-i-find-whether-my-output-fits-the-criteria-or-not#70331554
"""
ret = []
omax = max(orders) # generate combo for up to max of orders
# combine all sizes and get the sum and save to list
all_sizes = []
for i in range(1, omax 1):
combo = itertools.combinations_with_replacement(sizes, i)
for j in list(combo):
sj = sum(j)
all_sizes.append(sj)
all_sizes = list(set(all_sizes)) # remove duplicates
# print(f'all sizes: {all_sizes}')
# Read each value in the orders and check it in all_sizes.
for o in orders:
if o in all_sizes:
ret.append(True)
else:
ret.append(False)
return ret
# Start
res = processOrders([5, 12, 13, 20], [1, 2, 5, 10])
print(res) # [True, True, True, True]
res = processOrders([5, 12, 13, 100, 45], [4, 8, 12, 16])
print(res) # [False, True, False, True, False]
res = processOrders([1, 2, 3, 4], [16, 8, 12, 4])
print(res) # [False, False, False, True]
res = processOrders([27, 9, 6, 12], [7, 11])
print(res) # [False, False, False, False]
另一種使用數字的可整性的方法。
def processOrders(orders, sizes):
"""
Ref:
https://www.mathsisfun.com/definitions/divisible.html
https://stackoverflow.com/questions/70331554/how-can-i-find-whether-my-output-fits-the-criteria-or-not#70331554
"""
ret = []
for o in orders: # read each value in the orders
success = False
for s in sizes: # read each value in the sizes
if o % s == 0: # if order can be divided by size without remainder
ret.append(True)
success = True
break # get out of for s .. loop
if not success:
ret.append(False)
return ret
# Start
res = processOrders([5, 12, 13, 20], [1, 2, 5, 10])
print(res) # [True, True, True, True]
res = processOrders([5, 12, 13, 100, 45], [4, 8, 12, 16])
print(res) # [False, True, False, True, False]
res = processOrders([1, 2, 3, 4], [16, 8, 12, 4])
print(res) # [False, False, False, True]
res = processOrders([27, 9, 6, 12], [7, 11])
print(res) # [False, False, False, False]
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/382239.html