變化對棒切割（棒的大小可以改變）

Question

[這是一個任務，請不要給我的全部代碼。] 我需要寫接收兩個列表，一個與棒的股票功能（它們的大小而變化），以及一個與所述順序，並返回任一「假，[]」（如果這是不可能的回答順序）或「真，how_to」，其中how_to是在其中每個項目是所述杆的所使用的索引的列表按順序供應相應的物品。

例如：

stock = [100, 150] 
order = [30, 60, 90, 60] 
how_to = [0, 0, 1, 1] 

任何解決方案，它的工作原理是接受（[0,0,1,1]，[0,1,1,0]，[1,1,0,1]等）。該函數必須是遞歸的。

how_to = [] 
def process(stock, order): 

    stock_size = 0 
    order_size = 0 

    for i in order: 
     order_size += i 
    for i in stock: 
     stock_size += i 

    if order_size > stock_size: 
     return False, [] 

    elif len(order) == 0: 
     return True, how_to 

    else: 

     for i in range(len(stock)): 
      if len(stock) > 0: 
       if stock[i] >= order[0]: 
        stock[i] -= order[0] 
        how_to.append(i) 
        del order[0] 
        process(stock, order) 
      else: 
       return True, how_to 
     return False, [] 

到目前爲止，這是我寫的。但是，只有當how_to中的項目增加時（例如，解決方案使用庫存的順序出現），它才起作用。如過程（[60,70,50]，[45,5,25,30,55]）不起作用。我需要幫助解決它。

我知道我的解決方案不是動態的，但這是我能想出的。

有一些要求： （1）我不能在列表進行排序。 （2）我不能在函數中添加另一個參數。

Answer 1

首先，讓我們崩潰的程序的頭，方便閱讀。 總和方法彙總列表的元素。因此，您的ELIF之前一切崩潰到：

if sum(order) > sum(stock): 
    return False, [] 

接下來，解決您的爲閉環控制的邏輯。在規劃一個重要的概念是，你應該不變化爲 -loop參數，一旦你進入循環。在這種情況下，在循環內更改庫存是一個壞主意。相反，當你再次出現，傳遞的參數改變的副本，如

reduce = stock[:] # copy stock 
reduce[i] -= order[0] 
process(reduce, order.pop(0)) 

現在，你在遞歸的邏輯有缺陷，你永遠不使用返回結果。而不是讓how_to一個全局變量，你應該讓地方，讓你找到任何解決方案，並傳回的結果，將本切割。

的想法更像是這樣的：

for each rod in stock: 
    if I can cut the first rod of the order from this, 
     simulate making the cut 
     update the stock 
     recur on the remainder of the order 
     if that recursion works, 
      append the simulated cut to this solution, 
      return success 
# If I get here, I didn't find any solution 
return failure 

順便說一句，請注意，有一個空的解決方案列表相當於失敗。我不明白爲什麼這個任務也會返回True或False。

---

增加暗示的局部變量：

既然你只需要一個解決方案，how_to只是暫時的方便，如果不需要的領先就不會存在於所有布爾。該解決方案應該只存在中的返回值。

if len(order) == 0: 
    return True, [] 

... 
    found, how_to = process(reduce, order[1:]) 
    if found: 
     how_to.append(i) 
    return found, how_to 

在那裏，它是：如果發現了一個解決方案，N-1棒，然後簡單地追加你在這個迭代中所作的切割，並通過在N杆溶液向上行。