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

-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

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

回答

相关问题