Family: binpack
Authors: Kevin Braunsdorf, Marc W Mengel
Mail: [email protected]
Version: 1.5
Bugs: None known

Introduction

The classic CS problem with whose perfect solution in O(2**N), but we can do a pretty good one in order N memory and order N time.

Configuration

The shell variable $MACHINE_H is taken as the name of the machine.h file by an explode directive in binpack.c.
typedef ... VE;
A typedef for the in-core type for an element in a bin.

A bin itself is vector of these, that is pointer to the first one and a size_t count of the number in the bin.

typedef ... VEWEIGHT;
The scalar type for a weight (or size) that is the number that reflects the size on a given VE in a bin.
#define VE_MASS(Mx) (Mx)
Wraps any VE expression passed to the run-time functions (viz. w below) that compute a VEWEIGHT from a VE. This allows the selection of only part of the VE, or the address of the VE to be passed to the function.

The default passes the whole contents.

#define VE_MASS_DECL VE
Define the type a VEWEIGHT function (viz. w below) accepts. The default in binpack.h is the VE type.

Synopsis

#include "machine.h"
#include "binpack.h"

Description

Provides

size_t VEbinpack(VE *v, size_t n, VEWEIGHT (*w)(VE), VEWEIGHT b, size_t *puover)
This function does the work of packing VE's into bins. The items in the vector v are re-ordered such that, as the vector is walked, bins are formed from run of sequential elements.

Over-sizes items are moved to the end of the vector.

int VEassemble(VE *pVE, size_t n, VEWEIGHT (*w)(VE), VEWEIGHT b, int (*pfiDisplay)(VE *, size_t))
This function walks the vector to form the bins requested, each bin (and every over-sized element) is passed to the Display function as a unit.

A subtle point here is that the display function assemble calls may repack the bin it is processing by calling binpack (with a smaller size). This is quite useful in some application.

EXAMPLE

See the test main at the end of the module.

Diagnostics

None.

See Also

calloc(3), free(3), binpack(1), nushar(1)

To Do List

None. This code has not changed function in 20 years.

A related problem, which would be useful: this code doesn't know anything about "mutually exclusive" items. More complex problems could be solved if the weight function knew more about the context of the item in question (what was already in the bin, for example).

This would allow items to change weight based on placement, which is beyond the current tactic entirely (e.g. objects with both volume and temperature). 

$Id: binpack.html,v 6.8 2012/03/21 16:15:04 ksb Exp $