NP Complete, Bin Packing Problem
Bin Packing Problem
Given a collection of items of varying weights w1 w2 w3 etc,
and a set of bins with varying capacities c1 c2 c3 etc,
is it possible to pack all of the items into the bins?
Assume the total weight does not exceed the total capacity, else there is no solution.
Constant Capacity
One can assume all the bins have the same capacity without loss of generality.
If an algorithm works for bins with constant capacity,
and we are given a set of k bins with varying capacities,
let t be the largest capacity of any bin,
and replace each bin with a new bin having capacity 2t+1.
Then bring in k additional items, weighing 2t+1-ci.
Each of these items consumes more than half of a bin -
hence there is at most one new item per bin.
And if a bin contains none of these new items, some other bin holds two, which is impossible.
Therefore each bin is occupied by one new item,
and that leaves a remaining capacity of ci for the original items.
No Holes
It is sufficient to force the bins to be filled completely.
That is, the total weight equals the total capacity.
If the total weight is less, add items of unit weight until the totals are equal.
These items take up the slack in any partially filled bin.
Two Bins
The bin packing problem with no holes reduces immediately to asymmetric split.
It only takes two bins to become np complete.
Near Solutions
although bin packing is np complete, research continues.
Just type "bin packing problem" into google and you'll see what I mean.
People are interested in approximate solutions, or solutions under certain situations,
and there are many interesting results.
Alas, these will probably never make it to my website, for lack of time and resources.
Similar comments apply to most of the problems in this topic.
The traveling salesman problem, for example,
has also received a great deal of attention,
and there are algorithms that produce (nearly) the best solution for most "real world" graphs.
There's just so much math out there, as far as the eye can see in any direction,
and that's one of the things I hope to demonstrate with this website.
More Problems
There are many more np complete problems -
too many to describe here.
I think I've touched on the big ones.
Of course the $64 question is factorization.
Is factoring a composite number np complete?
If so, we'll all sleep better at night,
as this is the cornerstone of rsa encryption.
Chip away at this tantalizing problem if you like, in your spare time,
but remember, it has eluded the brightest minds of the past half century.