返回所需材料的可能組合批次的算法

-2

我遇到問題，例如需要使用300米皮革來構建沙發。返回所需材料的可能組合批次的算法

我的材料進來不同批次。

我的目標是找到最適合我的要求的組合。

通過上述批次，可能好比賽將是

300m 
200m + 100m 
200m + 50m + 30m + 20m 
200m + 40m + 40m + 10m 
200m + 40m + 30m + 20m + 10m 
No wastage for the above example

但如果我的批次： 40米百米 220米 250米

，則必須存在浪費，我的組合將是

220 + 100 with 20m wastage, 
250 + 100 with 50m wastage 
220 + 250 with 170m wastage

來源

2016-12-08 Gavin Yap

對於正在使用的批次數是否有任何意義（例如，批次越少越好）？ – FDavidov

您可以在O(n) t時間複雜。這個答案假設給定的批次已經排序。

這個想法是從兩側進行迭代，直到它們相遇，或者兩邊的總和變得小於所需的長度並跟蹤每個有效索引/索引的最小值。

假設我們有一批是

40m 100m 220m 250m 
^   ^

我們檢查，如果他們兩人或其中一方的總和可以單獨進行所需的長度。

即）40米<300米和250米<300米40米+250米<300米

所以，我們前進的起始位置由1

40m 100m 220m 250m 
    ^  ^

再次百米<300米&250米<300米不過百米+ 250米> 300米 - 由於這是一種可能性，而且我們需要更多的東西，因此我們需要標記與該指數相關的指數和浪費，並將終點位置迭代1

40m 100m 220m 250m 
    ^^

再說一次，他們每個人都不能製造300米，但他們可以一起製造300米，浪費較少。因此，我們更新了指數和浪費，並在下一次迭代中開始等於結束。

來源

2016-12-08 06:11:45 thebenman

你好，你的算法絕對是一個不錯的選擇。但是，我已經更新了第一個示例，可以組合許多批次來滿足要求。在你的情況下，只有2批次被選中。所以如果出現兩批不符合要求的情況，它將永遠不會滿足。 –

我自己對這個問題的解決方案可能不是最好的或有效的算法，但至少它確實給我一個可能的匹配列表（我認爲）。

首先，我需要篩選和排序我擁有的物料資源批次。僞代碼如下：

func filter_sort_batches(product, batches) 
    newlist = [] 
    product_keys = product.keys 

    foreach batch in batches: 
     score = 0 

     if split doesn't contain a product_key, ignore batch 

     if the split doesn't contain a product_key but also contain other keys that the product doesn't require, ignore batch 

     for each key in batch: 
      if product[key] >= batch[key]: 
       score += (product[key] - batch[key]) 
      else: 
       score += (batch[key] - product[key]) * product[key] 

     put [score, batch] to newlist 
    newlist.sort_by score, where the lowest score is the best

要返回比賽需要2個功能，該主要功能如下：

func find_match(list, product) 
    newlist = list.clone 
    matches = Array.new 
    find_match_recursive(newlist, product, matches, Array.new) 
    result = matches.sort_by score, where the lowest score is the best 
    print result

遞歸函數如下：

func find_match_recursive(list, product, matches, group) 
    return if list is empty 

    newlist = list.clone 
    tuple = newlist.shift 
    batch = tuple.last 
    new_group = group.clone 
    new_group << batch 

    if has_met_quantity(check_outsanding_materials(product, new_group)): 
     grp_tuple = score_group(new_group, product) 
     score = grp_tuple[0] 
     if score less than 2x of the sum of product's values: 
      add grp_tuple to matches 

    else: 
     # recurse to get the next batch and try to meet quantity check 
     find_match_recursive(newlist, product, matches, new_group) 

    #ignore the current recursion and skip to next batch in the list 
    find_match_recursive(newlist, product, matches, group)

其他功能我沒有包括僞代碼：

score_group: computes the wastage for each material used. 
check_outsanding_materials: calculate how much material is required after substracting the batches 
has_met_quantity: check if the above for any materials qty has met or not.

來源

2016-12-12 08:08:14

返回所需材料的可能組合批次的算法

回答

相關問題