标签: packing

我有一堆矩形物体,我需要将它们装入尽可能小的空间(这个空间的尺寸应该是2的幂).

我知道各种打包算法会将项目尽可能地打包到给定的空间中,但是在这种情况下我需要算法来计算出该空间应该有多大.

例如,说我有以下矩形

• 128*32
• 128*64
• 64*32
• 64*32

它们可以装入128*128的空间

 _________________
|128*32          |
|________________|
|128*64          |
|                |
|                |
|________________|
|64*32  |64*32   |
|_______|________|

但是如果还有160*32和64*64,则需要256*128空间

 ________________________________
|128*32          |64*64  |64*32  |
|________________|       |_______|
|128*64          |       |64*32  |
|                |_______|_______|
|                |               |
|________________|___            |
|160*32              |           |
|____________________|___________|

有哪些算法能够打包一堆矩形并确定容器所需的大小(功率为2,并且每个维度的给定最大大小)？

考虑:

struct mystruct_A
{
   char a;
   int b;
   char c;
} x;

struct mystruct_B
{
   int b;
   char a;
} y;

结构的尺寸分别为12和8.

这些结构是填充还是包装？

什么时候进行填充或包装？

注意:我不认为这是一个重复的问题,这是一个非背景包,挂起 git 与一个微妙的不同的错误消息.

在我的一个git存储库中,每次调用时(例如)git fetch,git打印:

Auto packing the repository in background for optimum performance.
See "git help gc" for manual housekeeping.

如果我git fetch反复做的话,它似乎每次都会打印出来,即使没有任何变化也无需git fetch做任何事情.这对我来说没有多大意义.它似乎也发生在其他网络操作中,例如git push和git pull.

该命令立即返回到提示,没有进一步的输出,我找不到在我的机器上运行的任何git进程.它似乎只发生在这个存储库中,并且只在这台机器上发生.git config -l | grep gc没有回报.

我该怎么做才能诊断或解决这个问题？

$ git --version 
git version 2.0.1

我使用的是OS X 10.9.

低级别位操作从来都不是我的强项.我将理解一些有助于理解按位运算符的以下用例.考虑...

int age, gender, height, packed_info;

. . .   // Assign values 

// Pack as AAAAAAA G HHHHHHH using shifts and "or"
packed_info = (age << 8) | (gender << 7) | height;

// Unpack with shifts and masking using "and"
height = packed_info & 0x7F;   // This constant is binary ...01111111
gender = (packed_info >> 7) & 1;
age    = (packed_info >> 8);

我不确定这段代码是什么以及如何完成的？为什么使用幻数0x7F？如何完成包装和拆包？

资源

我试图将不同尺寸的圆圈装入一个矩形容器中,而不是装在下面d3.js捆绑的圆形容器中d3.layout.pack.

这是我想要实现的布局:

我已经在这个问题上找到了这篇论文,但我不是一个全面理解这篇文章并将它们转换成代码的数学家......

任何人都可以建议我应该在哪里开始将其转换为d3.js布局插件,或者如果你有类似于这种布局的可视化气泡,请建议你采取任何方向来解决这个问题.

谢谢.

例如,我有一个class,

class naive {
public:
    char a;
    long long b;
    char c;
    int d;
};

根据我的测试程序,a对d被陆续建成,像

a-------
bbbbbbbb
c---dddd

- 意味着未使用

为什么C++不能让它变得更紧,比如

ac--dddd
bbbbbbbb

我有N项2D图像数据将是矩形的,我想尽可能高效地将它们打包成2个纹理的单个幂.

一个简单的非高效和天真的算法实现包装这些rects很容易鞭打,但我敢肯定人们已经提出算法尽可能节省空间.我发现了与光照贴图类似的各种参考,这与我正在寻找的类似,但是光照贴图的算法往往会考虑非矩形图像,这实际上使事情变得比我需要的更复杂.

有人有提示吗？算法或论文作者的名字我应该google？

谢谢.

在代码审查期间,我遇到了一些定义简单结构的代码,如下所示:

class foo {
   unsigned char a;
   unsigned char b;
   unsigned char c;
}

在其他地方,定义了这些对象的数组:

foo listOfFoos[SOME_NUM];

之后,将结构原始复制到缓冲区中:

memcpy(pBuff,listOfFoos,3*SOME_NUM);

此代码依赖于以下假设:a.)foo的大小为3,并且不应用填充,并且b.)这些对象的数组被打包,它们之间没有填充.

我已经在两个平台(RedHat 64b,Solaris 9)上使用GNU进行了尝试,并且它在两者上都有效.

以上假设是否有效？如果没有,在什么条件下(例如OS /编译器的变化)可能会失败？

假设我有一个完整的,无向图G,每个边都有一个距离.具有长度l的边(u,v)的含义是"点u和v不能彼此更接近于l".我的目标是将该图的节点放在一个平面中,这样就不会违反这些距离约束,并且这些点的凸包具有最小的总面积.举个例子,假设我有一堆电子元件要放在芯片上,每个电子元件会产生一些电气干扰.如果我将组件放得太近,它们就会开始相互干扰,使整个系统无法使用.假设每个点的最小距离应该来自彼此,那么将组件放在芯片上的最节省空间的方法是什么？

我不知道如何开始考虑这个问题.我也不知道问题可能会如何推广到更高维度的情况(将点装入超平面).有谁知道解决这个问题的好方法？

我有一组整数M和一个目标和k.我想找到M的子集,当它们加在一起时最接近k而不会过去.

例如:

M = {1, 3, 5, 5, 14}

k = 12

answer = {1, 5, 5}

because 1 + 5 + 5 = 11 and there is no way to make 12.

我有一个额外的约束,即子集最多可以包含4个元素.

在我的应用程序中,| M |的大小 可以很大(大约数千个元素).如果无法在合理的时间内找到最佳答案,我对至少给出"好"答案的解决方案感兴趣.

现在我通过生成10,000个随机子集并选择最接近的子集来解决这个问题,这个子集的效果比预期的要好但是很慢.我不确定这实际上有多远,但任何有关这方面的见解对我来说都很有趣.