Databases
StackOverflow2013
Postsdbo
POKnown algorithm for efficiently distributing items and satisfying minima?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POKnown algorithm for efficiently distributing items and satisfying minima?
    primarykey
    data
    text
    <p>For the following problem I'm wondering if there is a known algorithm already as I don't want to reinvent the wheel.</p> <p>In this case it's about hotel rooms, but I think that is rather irrelevant:</p> <pre><code>name | max guests | min guests 1p | 1 | 1 2p | 2 | 2 3p | 3 | 2 4p | 4 | 3 </code></pre> <p>I'm trying to distribute a certain amount of guests over available rooms, but the distribution has to satisfy the 'min guests' criteria of the rooms. Also, the rooms need to be used as efficiently as possible.</p> <p>Let's take 7 guests for example. I wouldn't want this combination:</p> <pre><code>3 x 3p ( 1 x 3 guests, 2 x 2 guests ) </code></pre> <p>.. this would satisfy the minimum criteria, but would be inefficient. Rather I'm looking for combinations such as:</p> <pre><code>1 x 3p and 1 x 4p 3 x 2p and 1 x 1p etc... </code></pre> <p>I would think this is a familiar problem. Is there any known algorithm already to solve this problem?</p> <p>To clarify:<br> By efficient I mean, distribute guests in such a way that rooms are filled up as much as possible (guests preferences are of secondary concern here, and are not important for the algorithm I'm looking for).<br> I <strong>do</strong> want all permutations that satisfy this efficiency criteria though. So in above example <code>7 x 1p</code> would be fine as well.</p> <p>So in summary:<br> Is there a known algorithm that is able to distribute items as efficiently as possible over slots with a <code>min</code> and <code>max</code> capacity, <strong>always satisfying</strong> the <code>min</code> criteria and <strong>trying to satisfy</strong> the <code>max</code> criteria as much as possible.</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USDecent Dabbler
    1. USDecent Dabbler
    plurals
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POKnown algorithm for efficiently distributing items and satisfying minima?
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POKnown algorithm for efficiently distributing items and satisfying minima?
      1. UScli_hlt
      1. VTFavorite
    3. VO
      singulars
      1. POKnown algorithm for efficiently distributing items and satisfying minima?
      1. This table or related slice is empty.
      1. VTUpMod
    1. CO"the rooms need to be used as efficiently as possible" it is not clear what your measure of efficeincy is.
      singulars
      1. POKnown algorithm for efficiently distributing items and satisfying minima?
      1. USRaedwald
    2. COShould we assume that the guests come in groups (each group with a specific number of people) and that each room can only host a single group, like in a real hotel?
      singulars
      1. POKnown algorithm for efficiently distributing items and satisfying minima?
      1. UShan
    3. COYour question is confusing. What do you mean by "efficient"? For example, why is 3x3p (3 rooms total) inefficient, but 3x2p + 1x1p (4 rooms total) efficient? It seems that the question is missing a cost or efficiency function.
      singulars
      1. POKnown algorithm for efficiently distributing items and satisfying minima?
      1. USAndrew Schulman
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload