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

gile · 发表于 2014-12-6 17:31:01

数据集怎么样？

gile · 发表于 2014-12-6 17:32:33

double dbls[] ={ 80， 26， 57， 18， 8， 45， 16， 22， 29， 5， 11， 8， 27， 54， 13， 17， 21， 63， 14， 16， 45， 6， 32， 57， 24， 18， 27， 54， 35， 12， 43， 36， 72， 14， 28， 3， 11， 46， 27， 42， 59， 26， 41， 15， 41， 68};
输入 bin 大小： 80
测试 = TRUE
BinNum = 1， BinSize = 80.000000 （80.000000 ）
BinNum = 2， BinSize = 80.000000 （45.000000 35.000000 ）
BinNum = 3， BinSize = 80.000000 （54.0000000 26.000000 ）
BinNum = 4， binSize = 80.000000 （54.000000 26.000000 ）
BinNum = 5， BinSize = 80.000000 （59.000000 21.000000 ）
BinNum = 6， binSize = 80.000000 （63.000000 17.000000 ）
BinNum = 7， binSize = 80.000000 （68.000000 12.000000）
BinNum = 8， binsize = 80.000000 （27.000000 24.000000 18.000000 11.000000 ）
BinNum = 9， BinSize = 80.000000 （72.000000 8.000000 ）
BinNum = 10， binsize = 80.000000 （45.000000 29.000000 6.000000 ）
BinNum = 11， BinSize = 80.000000 （57.0000000 18.000000 5.000000 ）
BinNum = 12， binsize = 79.000000 （43.000000 36.000000 ）
BinNum = 13， BinSize = 79.000000 （57.000000 22.000000 ）
BinNum = 14， binsize = 79.0000000 （41.0000000 27.000000 11.000000 ）
BinNum = 15， BinSize = 78.000000 （46.000000 32.000000 ）
BinNum = 16， BinSize = 78.000000 （42.0000000 28.000000 8.000000 ）
BinNum = 17， BinSize = 78.000000 （16.000000 16.000000 15.000000 14.000000 14.000000 3.000000 ）
BinNum = 18， binSize = 68.0000000 （41.000000 27.000000 ）
BinNum = 19， BinSize = 13.000000 （13.000000）

gile · 发表于 2014-12-6 19:06:43

仍然使用首次拟合递减算法，一些稍微短的代码，但是比gile的变体慢:

copy

(defun binpack ( l s / a b c x )
    (foreach x (vl-sort-i l '>)
        (setq c nil
              x (nth x l)
              a (vl-member-if '(lambda ( b ) (cond ((
              b (append (reverse c) (cons (cons x (car a)) (cdr a)))
        )
    )
)

copy

(setq l '(80 26 57 18 8 45 16 22 29 5 11 8 27 54 13 17 21 63 14 16 45 6 32 57 24 18 27 54 35 12 43 36 72 14 28 3 11 46 27 42 59 26 41 15 41 68)
      s  80
)
_$ (binpack l s)
((80) (8 72) (12 68) (17 63) (21 59) (22 57) (5 18 57) (26 54) (26 54) (32 46) (35 45) (6 29 45) (36 43) (8 28 42) (11 27 41) (11 27 41) (3 18 24 27) (14 14 15 16 16) (13))
_$ (length (binpack l s))
19

gile，如果用整数测试，要小心
vl-sort

gile · 发表于 2014-12-6 22:06:55

这是我的条目#include。
#包含。
#包含。
。
类BinKey；。
typedef std::向量bin；。
typedef std::multimapBinMap；。
。
类BinKey。
{。
私有：。
双m_size；。
布尔m_isFull；。
公共：。
BinKey（）。
：m_size（0），m_isFull（false）{}。
BinKey（双val）。
：m_size（val），m_isFull（false）{}。
bool运算符。
{。
返回这个->size（）>rhs.size（）；。
}。
双size（）const{返回m_size；}。
bool isFull（）const{返回m_isFull；}。
空是完整的（bool val）{m_isFull=val；}。
}；。
。
类BinPacker。
{。
私有：。
m_bin；。
BinMapm_binMap；。
constsize_tm_binSize；。
。
公共：。
BinPacker（const bin&bin，size_tbinSize）：m_bin（bin），m_binSize（binsize）。
{。
}。
。
~BinPacker（无效）。
{。
}。
。
无效的值（）。
{。
std::排序（m_bin.begin（），m_bin.end（），std::更大());。
双minVal=m_bin.back（）；。
。
为（自动vecIter=m_bin.begin（）； vecIter！=m_bin.end (); ++vecIter）。
{。
如果（m_binMap.size () == 0）。
m_binMap.insert（std::make_pair（BinKey（）， bin()));。
。
bool擦除=false；。
BinMap::迭代器lastIter；。
。
为（自动映射=m_binMap.begin（）；映射！=m_binMap.end (); ++映射）。
{。
const双siz=m_binSize-mapIter->first.size（）；。
if（！ mapIter->first.isFull () && siz>=*vecIter&&*vecIter。
{。
lastIter=mapIter；。
擦除=真；。
休息；。
}。
}。
如果（擦除）。
{。
BinKey newKey（lastIter->first.size（）+*vecIter）；。
如果（m_binSize-newKey.size（）。
newKey.isFull（真）；。
自动m_binMap.insertd::make_pair（newKey， bin()));。
lastIter->second.push_back（*vecIter）；。
thisIter->second.swap（lastIter->秒）；。
m_binMap.erase（lastIter）；。
}。
其他。
{。
如果（*vecIter。
{。
自动d::=m_binMap.insert（std::make_pair（BinKey（*vecIter）， bin()));。
thisIter->second.push_back（*vecIter）；。
}。
}。
}。
}。
}；。
。

gile · 发表于 2014-12-7 04:57:36

很好，丹尼尔（即使我真的不能读C）。我也想过一种更OOP的方法，但我没有走得更远，因为我认为与简单的方法相比，它并没有多大意义，而且我倾向于在这些挑战中选择简洁。using System.Collections.Generic;。
使用 System.Linq;。
。
命名空间 BinPacking。
{。
公共类 Bin。
{。
私人双人_size;。
public double FreeSpace { get; private set; }。
public List Content { get; private set; }。
公共箱（双倍大小，双倍值）。
{。
_size = 大小;。
自由空间 = 大小 - 值;。
Content = new List（） { value };。
}。
公共布尔尝试插入（双值）。
{。
if （值 > FreeSpace）。
返回 false;。
自由空间 -= 值;。
Content.Add（value）;。
返回 true;。
}。
}。
。
公共类 BinPacker。
{。
私人双人_size;。
public List Content { get; private set; }。
公共 BinPacker（IEnumerable source， Double Size）。
{。
_size = 大小;。
内容 = 新列表（）;。
填充（源，OrderByDescending（x => x））;。
}。
。
私有空洞填充（IOrdered枚举源）。
{。
foreach（源中的双项）。
{。
插入的布尔 = 假;。
前（内容中的箱）。
{。
如果（bin.尝试插入（项目））。
{。
插入 = 真;。
休息;。
}。
}。
如果（！插入）。
{。
Content.Add（new Bin（_size， item））;。
}。
}。
}。
}。
}。
。

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

发表回复

精选推荐