ゴミ箱のソートアルゴリズム

Question

私は仕事で実際の世界の問題を抱えていますが、私はそれをPythonで解決することを望んでいましたが、解決する正しいアルゴリズムを見つけることができません。 私は固定サイズの穴が付いたゴミ箱を持っており、特定のサイズのゴミ袋をいくつか捨てる必要があると言います。各バッグは、具体的に正しいサイズでなければなりません。ゴミ箱の最小数を使用してゴミを捨てるためにどのようなアルゴリズムを使用できますか？

Answer 1

これはビンのパッキングやナップザックの問題のようです。どちらもNP困難であるため、どちらの問題に対しても多項式時間の最適解は存在しません。しかし、「近い」最適解を保証することができる実装が容易なヒューリスティックアルゴリズムが多数存在する。

最もよく知られているのは、First Fit an Best Fitです。これらのアルゴリズムはどちらも、使用されるビンの数が最適解で使用されるビンの数の1.7倍を超えないようにビンにアイテムをパックすることが保証されています。これらのアルゴリズムの詳細については、hereを参照してください。

次のようになります。Pythonで最初のフィットを使用して、非常に単純な例：

import random 

bin_capacity = 1.0 
bins = [[]] 
bin_stats = [0.0] # used to keep track of how full each bin is 
jobs = [random.uniform(0.0,1.0) for i in range(100)] 
for job in jobs: # iterate through jobs 
    job_assigned = False 
    for i in range(len(bin_stats)): 
     if job + bin_stats[i] <= bin_capacity: 
      # if job will fit into bin, assign it there 
      bins[i].append(job) 
      bin_stats[i] += job 
      job_assigned = True 
      break 
    if not job_assigned: 
     # if job doesn't fit into any bin, open a new bin 
     bins.append([job]) 
     bin_stats.append(job) 

for i in range(len(bins)): 
    print "Bin {:} is {:.2f}% full and contains the following jobs".format(i,bin_stats[i]*100) 
    for job in bins[i]: 
     print "\t",job