标签: bin-packing

这是我的问题:

• 有n家公司分销产品.
• 所有产品应在k天内分发
• 公司Ci的分销产品应该是连续的 - 这意味着它可以在2,3,4,5天分发,但不能分发2,3,6,7
• 公司Ci在第j天的分发产品数量应该在第j-1天小于(或相等)(如果在第j-1天有任何数据)
• 第i天和第j天之间的分布式产品之间的差异不应大于1

例:

我们有3天的时间来分发产品.A公司的产品:a,a,a,a,a.B公司产品:b,b,b.C公司产品:c,c

公平分配: [aab,aabc,abc]

分配无效: [aabc,aabc,ab]因为第1天有4个产品,第3天有2个产品(差异> 1)

分配无效: [abc,aabc,aab]因为第1天有一个产品A,第二天有2个产品A,所以产品A的分配不是不减少

编辑, 如果有一个案例,使公平分配不可能请提供简短说明,我会接受答案

我正在寻找一种能够以最有效的方式解决我的问题的算法.

问题描述:

我有一个项目列表(只允许正整数)和相同容量的固定数量的箱子.到目前为止,我考虑过分支定界算法,但我不确定它是否是这种情况下的最佳方法.

例:

给出一个项目列表:

(3, 4, 4, 2, 3, 9, 2)

还有三个容量为9的容器,我需要将它们包装起来:(物品的顺序无关紧要)

[3, 4, 2], [4, 3, 2], [9]

我认为这是bin-packing问题的变种(我知道它是NP-complete),但是由于我不是想尽量减少使用的bin数量,我想知道是否有更好的解决方案.

Fuseki.net的rect http://fuseki.net/rect/imgs/images-final-2007-10-14-13-35-45.gif 这是在python中实现的(更多测试)

我对上面的图像(在python中实现)使用Packery.js jQuery插件进行基于js/DOM的bin打包感兴趣.Packery可以从左到右,从上到下工作,但我想知道是否使用圆形边界框而不是视口,因为它的边界可以解决问题.

最终我想用它来呈现许多尺寸和比例都很大的图像缩略图.

任何代码示例或其他指针都将受到高度赞赏.

这是一个CodePen供您玩:http://codepen.io/anon/pen/zytBK

我有矩形和 GridLayout，这些矩形的宽度和高度是相同的。所以布局将矩形的位置设置为如下图所示。

这就是问题：如果我的矩形的宽度和高度不同，那么布局以紧凑的方式放置矩形位置的算法是什么？

我试图将我的 data.frame/data.table 的一列分成三组，所有组的总和相等。

数据首先从最小到最大排序，这样第一组将由大量具有小值的行组成，而第三组将由少量具有大值的行组成。这是在精神上完成的：

test <- data.frame(x = as.numeric(1:100000))
store <- 0
total <- sum(test$x)

for(i in 1:100000){

  store <- store + test$x[i]

  if(store < total/3){

    test$y[i] <- 1

  } else {

      if(store < 2*total/3){

        test$y[i] <- 2

      } else { 

        test$y[i] <- 3

      }     
  }    
}

虽然成功，但我觉得一定有更好的方法（也许是我缺少的一个非常明显的解决方案）。

• 我从不喜欢使用循环，尤其是嵌套 ifs，当矢量化方法可用时 - 即使有 100,000 多条记录，这段代码也会变得很慢
• 这种方法将变得不可能复杂到编码到更多的组（不一定是循环，而是 ifs）
• 需要预先订购色谱柱。可能无法绕过这个。

作为一个细微差别（并不是说它有区别），但要求和的数据并不总是（或永远）是连续的整数。

这是背包算法还是装箱算法？我找不到确切的解决方案，但基本上我有一个固定的矩形区域，我想用完美的正方形填充它，这些正方形代表我的物品，其中每个物品都有不同的重量，这会影响它们相对于其他物品的大小。

它们将从左上到右下从大到小排序。

另外，即使我需要完美的正方形，最终也允许一些非均匀缩放填充整个空间，只要它们仍然保留其相对面积，并且非均匀缩放是用尽可能少的量完成的。

我可以使用什么算法来实现这一目标？

我有一个动态的编程问题,我花了几个小时研究无济于事.

第一部分很简单:你有一个背包物品,你必须最大化这些物品的价值,同时保持低于一定的重量.

问题的第二部分是相同的,除了现在还有一个项目限制.例如:

您可以放入包中的物品的最大价值是什么,以便在重量和物品限制的情况下最大化价值？

我不知道如何实现这个问题的第二部分,我正在寻找一般的算法.

我有一个n × m网格和一组polyominos.我想知道是否可以将它们打包到网格中:不允许重叠或旋转.

我希望像大多数包装问题一样,这个版本是NP难以近似的,所以我不期待任何疯狂,但是算法可以在25×25左右的网格上找到合理的包装并且相当全面,大约10×10会很好.(我的瓷砖大多是tetrominos - 四个块 - 但它们可能有5-9 +块.)

我会接受任何人提供的任何东西:算法,论文,可以调整的现有程序.

我有不规则的形状（想想地理边界），我需要用一组不同大小的正方形填充，而不重叠。应优先考虑使用尽可能大的正方形。到目前为止，我的方法是以增量循环图像的长度/宽度，并检查 (x,y) 处的正方形是否有效。如果是这样，请将方块保存在那里并将该区域标记为无效。然后我对我拥有的每个正方形尺寸重复该过程。它做了我想要的事情，但对于实际的小增量来说太慢了。如果我尝试在每个正方形维度上使用 else/if 一次性完成此操作，则最小的正方形将占主导地位。我也不能保证正方形大小的最优性。

nim[mask] = .5
nim[~mask] = 0
cim = nim.copy()

inc = 500
dims = [4000, 2000, 1000, 500]

regions = []
for d in dims:
    for x in range(0, nim.shape[0], inc):
        for y in range(0, nim.shape[1], inc):
            if (np.count_nonzero(cim[x:x+d, y:y+d])/(d*d) < .0001):
                nim = rect(nim, y, x, d, d, 1)
                cim = blocc(cim, y, x, d, d, 1)
                regions.append([x,y,d])
                
plt.imshow(nim)
plt.show()

其中 rect() 和 blocc() 分别绘制区域和填充区域的边。