Bin packing problems

Pack items (often with given weights, sizes, or lengths) into bins or containers with capacity constraints using algorithms like first-fit, first-fit decreasing, or finding optimal packings.

3 questions · Standard +0.3

Sort by: Default | Easiest first | Hardest first
OCR Further Discrete AS 2024 June Q7
13 marks Standard +0.3
7 Six items need to be packed into bins. Each bin has size \(k\), where \(k\) is an integer. The sizes of the items are \(\begin{array} { l l l l l l } 8 & 5 & 4 & 7 & 3 & 3 \end{array}\)
  1. Show a way to pack the items into two bins of size \(k = 18\).
  2. If exactly three bins are needed, determine the possible values of \(k\).
  3. Use the first-fit method to pack the items into bins of size 12.
  4. Explain why, in general, the first-fit algorithm does not necessarily find the most efficient solution to a packing problem. A possible way to calculate the run-time of the first-fit method is to count for each item the number of bins, excluding full bins, that are considered before the bin where each item is packed. The total count for all packed items is then used to calculate the run-time of the method.
  5. Determine the total count for the packing used in part (c). A student says that when \(k = 13\) the total count is 0 because the first bin fills up before the second bin is considered.
  6. Explain why the student's argument is not correct.
  7. Determine the least possible value of \(k\) for which the total count is 0 . \section*{END OF QUESTION PAPER}
OCR Further Discrete AS Specimen Q6
8 marks Standard +0.8
6 The following masses, in kg, are to be packed into bins. $$\begin{array} { l l l l l l l l l l } 8 & 5 & 9 & 7 & 7 & 9 & 1 & 3 & 3 & 8 \end{array}$$
  1. Chloe says that first-fit decreasing gives a packing that requires 4 bins, but first-fit only requires 3 bins. Find the maximum capacity of the bins. First-fit requires one pass through the list and the time taken may be regarded as being proportional to the length of the list. Suppose that shuttle sort was used to sort the list into decreasing order.
  2. What can be deduced, in this case, about the order of the time complexity, \(\mathrm { T } ( n )\), for first-fit decreasing?
OCR Further Discrete 2021 November Q1
8 marks Moderate -0.3
1 Sam is packing for a holiday. The table shows the mass of each item to be packed.
Item\(A\)\(B\)\(C\)\(D\)\(E\)\(F\)\(G\)\(H\)
Mass (kg)343.52.567.585
Sam's bags can each carry 10 kg , but no more.
  1. Use first-fit to show a possible packing that Sam could use. Indicate the items by using the letters \(A , B , \ldots\) rather than their masses. The total mass of the 8 items is 39.5 kg . Sam says that this means they can be packed using just 4 bags.
  2. Explain why Sam cannot pack the items using just 4 bags. Sam is only allowed to take 4 bags. Each item is given a value out of 20 representing how important it is to Sam.
    Item\(A\)\(B\)\(C\)\(D\)\(E\)\(F\)\(G\)\(H\)
    Mass (kg)343.52.567.585
    Value610121016122014
  3. Sam wishes to pack items with a large total value.