标签: packing

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

问题描述:

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

例:

给出一个项目列表:

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

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

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

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

我有一个连接的形状,由放在一起的正方形组成,例如,取一个方形纸,沿着现有的线条绘制一条线,该线条在其开始处结束并且不会交叉.

现在的目标是找到一个算法(而不是强力),用尽可能少的非重叠矩形填充这个形状.

我正在寻找最佳解决方案.从图像中可以看出,天真贪婪的方法(采取最大的矩形)不起作用.

(最佳)

(贪婪)

我的场景是顶点缩减,但我确信还有其他用例.

注意:此问题似乎很基本,但我无法在其他地方找到解决方案.还有,这个问题NP难吗？

编辑:我刚刚意识到,在我的场景中,用尽可能少的非重叠三角形填充形状会产生更好的结果.

我正在尝试使用python在正方形中对随机封闭的包装球进行建模.球体不应重叠, 但我不知道如何做到这一点

我到目前为止:

码:

import random, math, pylab

def show_conf(L, sigma, title, fname):
    pylab.axes()
    for [x, y] in L:
        for ix in range(-1, 2):
            for iy in range(-1, 2):
                cir = pylab.Circle((x + ix, y + iy), radius=sigma,  fc='r')
                pylab.gca().add_patch(cir)
    pylab.axis('scaled')
    pylab.xlabel('eixo x')
    pylab.ylabel('eixo y')
    pylab.title(title)
    pylab.axis([0.0, 1.0, 0.0, 1.0])
    pylab.savefig(fname)
    pylab.close()

L = []
N = 8 ** 2

for i in range(N):
    posx = float(random.uniform(0, 1))
    posy = float(random.uniform(0, 1))
    L.append([posx, posy])

print L

N = 8 …

我需要将四个带符号的字节打包成32位整数类型.这就是我的目标:

int32_t byte(int8_t c) { return (unsigned char)c; }

int pack(char c0, char c1, ...) {
  return byte(c0) | byte(c1) << 8 | ...;
}

这是一个很好的解决方案？它是便携式的(不是通信意义上的)吗？是否有现成的解决方案,或许可以提升？

问题我最关心的是将负位从char转换为int时的位顺序.我不知道应该是什么样的正确行为.

谢谢

我以为我理解C/C++如何处理结构成员对齐.但是我在Visual Studio 2008和2010中的特定安排中得到了奇怪的结果.

具体来说,我发现由char,short和char组成的结构被编译成6字节结构,即使启用了4或8字节打包.我不知道为什么会这样.我可以理解一个4字节的结构.我或许可以理解一个8字节的结构.但我认为当启用4字节打包时,6字节结构是不可能的.

一个演示问题的程序是:

#include <iostream>
using namespace std;

#pragma pack (4)

struct Alignment
{
 char c1;
 short s;
 char c2;
};

#define REPORT_VAR_POSITION( structName, varName ) cout << "Member '" << #varName << "' sits at byte # " << offsetof( structName, varName ) << "." << endl;

int main(int argc, char* argv[])
{
 cout << "Sizeof struct Alignment is " << sizeof( Alignment ) << " bytes." << endl;
 REPORT_VAR_POSITION( Alignment, c1 );
 REPORT_VAR_POSITION( Alignment, s ); …

以下是我要实现的目标:

• 我需要将32位IEEE浮点数打包成30位.
• 我想通过将尾数的大小减少2位来实现这一点.
• 操作本身应该尽可能快.
• 我知道会丢失一些精度,这是可以接受的.
• 如果这个操作不会破坏像SNaN,QNaN,无穷大等特殊情况,那将是一个优势.但我已经准备好在速度上牺牲这个.

我想这个问题包括两部分:

1)我可以简单地清除尾数的最低位吗？我试过这个,到目前为止它的确有效,但也许我在寻找麻烦......有点像:

float f;
int packed = (*(int*)&f) & ~3;
// later
f = *(float*)&packed;

2)如果有1)失败的情况,那么实现这一目标的最快方法是什么？

提前致谢

我希望制作一个类似于piccsy.com的3列布局.给定了许多宽度相同但高度不同的图像,对它们进行排序的算法是什么,以便列长度的差异最小？理想情况下用Python或JavaScript ...

非常感谢您的帮助!

马丁

我的作业有问题。我一直在搜索 stackoverflow 和其他网站，看看我正在处理哪种问题，结果我不确定这是背包问题还是垃圾箱包装问题。这是问题所在：

一位老太太买了N件产品，每件产品的重量（kg）不同，她想把所有的东西都装进一个能装K公斤的袋子里。找出权重之和尽可能接近 K 的对象集。

我正在尝试打包一个结构，在64 位32 位 Windows上使用 g++ 。

struct Foo
{
    uint8_t a;
    uint32_t b;
} __attribute__((packed));


int main(int argc, char *argv[])
{
    qDebug() << "sizeof(Foo):" << sizeof(Foo);
    return 0;
}

这输出 8. 我尝试过的其他事情：

{ uint8_t a; } // Gives 1, correct.
{ uint8_t a; float b; } // Gives 8, expected 5.
{ uint8_t a; uint16_t b; } // Gives 4, expected 3.
{ uint16_t a; uint8_t b; uint8_t c; } // Gives 4, correct.

所以看起来结构体是打包的，但sizeof在某些情况下会被四舍五入？（实际上，在写完这个问题后，我想我可以回答它，但无论如何我都会将其发布以供后代使用。）

编辑：其实我不知道。我以为 …

我遇到了C#和C++之间的互操作问题,我通过本机代码和托管代码中定义的结构在应用程序的两个"端"之间共享内存.本机端的结构定义如下:

#pragma pack(push, 1)
        struct RayTestCollisionDesc {
                btVector3 hitPosition;
                btRigidBody* hitBody;

                RayTestCollisionDesc(btRigidBody* body, btVector3& position)
                        : hitBody(body), hitPosition(position) { }
        };
#pragma pack(pop)

并且在托管(C#)端定义了类似的结构.在C#上,结构大小是20个字节(正如我在32位系统上所期望的那样).但是,尽管有这个pragma pack指令,C++大小的结构大小仍然是32.为了清楚起见,这里sizeof()是每个类型的C++:

sizeof(btVector3) : 16 
sizeof(btRigidBody*) : 4
sizeof(RayTestCollisionDesc) : 32

显然pragma pack,只是指结构成员之间的打包,而不是结构末尾的填充(即对齐).我也试过添加,__declspec(align(1))但没有效果,MSDN本身确实说"__declspec(align(#))只会增加对齐限制."

FWIW我正在使用VS2013编译器(Platform Toolset v120).

有没有办法将结构大小"强制"为20个字节？