-= { Challenge } =-FOB mini grid(Bin packing-Subset Sum)Lispers请加入

gile · 发表于 2014-12-5 09:56:26

如果有人可以正确地对这个问题进行分类，请让我知道，但认为这是一个垃圾箱包装问题或子集总和问题，也许是背包问题的一个现实世界的例子，如果需要的话，什么挑战，一个临时的军事基地在甜点中间，在国外必须自己发电，即使它是在一个地方连接到一个国家的电网基地，也不想依赖外国的电网，这些底座将具有许多不同的组件，每个组件需要不同的功率，例如，将有30个坯料@ 14.4kW，每个2个换尿布站@ 12.34kW4急救@ 15.3kW等..... 他们将拥有一个60kW的发电机，理想情况下，或者如果发电机并联为电网供电，您将获取总功率并除以60（如果剩余功率再加1），这将是所需的发电机总数，这些发电机直接为组件供电，因此，除非您以总和等于发电机总输出的方式组合组件，否则您不会使用所有发电机的可用功率，目标是将组件组合在一起，以便它们需要最少的生成器，问题，Generator OutPut - 发电机可以产生的总功率。
每个组件都需要电源的集合，没有组件需要超过发电机输出，因此1组件功率永远不会超过发电机输出。
每个组件可以有 1 个或多个，挑战在于获取组件的集合，并将它们放入总和等于或小于生成器输出的组中，以便组件需要最少数量的生成器。你可以只使用双打或实数的列表，。

本帖以下内容被隐藏保护；需要你回复后，才能看到！

游客，如果您要查看本帖隐藏内容请回复

gile · 发表于 2014-12-5 11:00:35

哦，是的，只是为了扔进去，
假设你的电脑每秒可以计算出1，000，000种不同的组合。
只需1秒即可计算20个项目的所有不同组合。
只需36年即可计算出50个项目的所有不同组合

gile · 发表于 2014-12-5 15:02:20

嗨，这是一个简单的首次适合递减装箱C#实现。静态列表 > BinPack(IEnumerable  source，double packSize)。
{。
var groups = source。
，GroupBy(x => x)。
，order by descending(g = > g . Key)。
，Select(g => g.ToList())。
，to list()；。
var result = new List  >()；。
while(组，Count > 0)。
{。
var List = new List ()；。
var I = 0；。
while (i  0)。
{。
如果(列表，Sum() + groups[i][0] 。
{。
列表，添加(组[I][0])；。
组[i]，remove at(0)；。
if (groups[i].Count == 0)。
{。
组，remove at(I)；。
}。
}。
否则。
{。
i++；。
}。
}。
结果，添加(列表)；。
}。
返回结果；。
}。

gile · 发表于 2014-12-5 16:57:02

谢谢gile！！
输出看起来很棒，需要多盯着它看一会儿才能让它吸收。
...
我希望我能每周借你一两次大脑。

gile · 发表于 2014-12-5 17:35:53

gile · 发表于 2014-12-5 17:52:55

gile · 发表于 2014-12-6 04:04:39

一个LISP版本：

copy

(defun binPack (packsize source / insert result)
  (defun insert (x lst)
    (cond
      ((null lst) (list (list x)))
      ((
       (cons (cons x (car lst)) (cdr lst))
      )
      (T (cons (car lst) (insert x (cdr lst))))
    )
  )
  (foreach x (vl-sort source '>)
    (setq result (insert x result))
  )
)

本地函数中的time循环也是如此，以避免递归（AutoLISP不优化尾部递归）。

copy

(defun binPack (packsize source / insert result)
  (defun insert (x lst / done acc)
    (while (not done)
      (cond
        ((null lst)
         (setq acc  (reverse (cons (list x) acc))
               done T
         )
        )
        ((> (+ x (apply '+ (car lst))) packSize)
         (setq acc (cons (car lst) acc)
               lst (cdr lst)
         )
        )
        (T
         (setq acc  (append (reverse (cons (cons x (car lst)) acc)) (cdr lst))
               done T
         )
        )
      )
    )
    acc
  )
  (foreach x (vl-sort source '>)
    (setq result (insert x result))
  )
)

gile · 发表于 2014-12-6 05:47:37

一个更简单的C#实现：
私有静态列表
>BinPacking（IEnumerable
源代码，双packSize）
{
var结果=新列表
>（）
foreach（source.OrderByDescending中的var项（x=>x））
{
var done=false
用于（int i=0；i
{
var list=结果[i]
if（item+list.Sum（）
{
列表。添加（项）
done=true
中断
}
}
如果（！完成）
{
＜div＞var list＝新列表＜double＞（｛item｝）
结果。添加（列表）
}
}
返回结果
}