Subset algorithm

[papasierra]

Hello,

I am looking for an algorithm to do the following:

Given a set of real numbers:
- Divide them into subsets,
- Each number is to be used exactly once,
- The sum of all the numbers in a subset may not exceed a given value,
- The minimum number of subsets is to be used.

Any suggestions for this subset / combination algorithm?

Regards
PapaSierra

[Zachm]

You may want to take a look at:
http://en.wikipedia.org/wiki/Bin_packing_problem#_note-2

The Bin Packing problem is quite similar to the problem you described.
The simplest strategies for a heuristic solution to this problem are
First Fit Decreasing or Best Fit Decreasing.

These strategies may not yield an optimal solution to this problem, but since the general case of this problem is NP-Hard, it is highly unlikely that there is an optimal polynomial solution.

Best of luck !

[papasierra]

Many thanks for the quick reply! I will have a look at the link.
Regards
PapaSierra

[santipray]

You may want to take a look at:
http://en.wikipedia.org/wiki/Bin_packing_problem#_note-2

The Bin Packing problem is quite similar to the problem you described.
The simplest strategies for a heuristic solution to this problem are
First Fit Decreasing or Best Fit Decreasing.

These strategies may not yield an optimal solution to this problem, but since the general case of this problem is NP-Hard, it is highly unlikely that there is an optimal polynomial solution.

Best of luck !


It was another bin packing algorithm, right?but why the most widely used is BF and FF?

[Zachm]

It was another bin packing algorithm, right?but why the most widely used is BF and FF?

I never said that these algorithms are best or are most widely used, I only suggested that they are easy to implement.

Regards,
Zachm