Scribd
Upload
10 views2 pages

As Binpacking JR

The document outlines a bin packing problem where items of varying weights must be placed into bins with a maximum capacity of 10 pounds. Two algorithms are provided: First Fit, which places items in the first available bin, and First Fit Increasing, which sorts items by weight before packing. Sample input and output are given to illustrate how to determine the weight of each bin used for both algorithms.

Uploaded by

CK
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
10 views2 pages

As Binpacking JR

The document outlines a bin packing problem where items of varying weights must be placed into bins with a maximum capacity of 10 pounds. Two algorithms are provided: First Fit, which places items in the first available bin, and First Fit Increasing, which sorts items by weight before packing. Sample input and output are given to illustrate how to determine the weight of each bin used for both algorithms.

Uploaded by

CK
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
You are on page 1/ 2

ACSL

ALL-STAR American Computer Science League Program #2


Bin Packing Junior

PROBLEM: You have a set of "bins". Each bin has a capacity of 10 pounds. You are
given items weighing from 1 to 10 pounds each. The goal is to place the items in the bins
such that each bin is packed as close to capacity as possible. For example, if you have
items weighing 4, 3, 7, and 6, you could fit them into 2 bins: 4 + 6 in bin #1, and 3 + 7 in
bin #2. There would be no wasted capacity, as both bins are filled to capacity. However,
if you place 4 +3 in bin #1, you'd need to place 7 and 6 in separate bins, thereby, using 3
bins. There would be 3+3+4=10 pounds of extra capacity. Given 2 rules for placing items
in bins, determine the weight of each bin that needs to be used.

1. First Fit – Starting with bin #1, place the items, in the order given, in the first bin in
which they fit.

2. First Fit Increasing – Sort the items from lightest to heaviest. Then place the items,
starting with the lightest and bin #1, in the first bin in which they fit.

INPUT: There will be 5 input lines. Each line will have a list of item weights. The list
will end with a weight of zero.

OUTPUT: For each line of input print in order, starting with bin #1, the weight of each
non-zero bin used for each of the two algorithms. The output lines will be in the order of
the rules above unless labeled otherwise. Both answers must be correct to get a point.

SAMPLE INPUT SAMPLE OUTPUT

1. 2, 3, 5, 7, 4, 0 1. 10, 7, 4
2. 1, 1, 3, 5, 2, 6, 0 9, 5, 7
3. 9, 8, 7, 6, 5, 3, 0 2. 10, 8
4. 2, 2, 2, 3, 1, 2, 4, 0 7, 5, 6
5. 2, 7, 3, 6, 4, 4, 5, 5, 1, 0 3. 9, 8, 10, 6, 5
8, 6, 7, 8, 9
4. 10, 6
9, 7
5. 10, 9, 8, 10
10, 9, 5, 6, 7
ACSL
ALL-STAR American Computer Science League Program #2
Bin Packing Junior

TEST DATA

TEST INPUT TEST OUTPUT

1. 1, 5, 3, 5, 3, 0 1. 9, 8
7, 10
2. 2, 2, 4, 2, 3, 5, 2, 0 2. 10, 10
8, 7, 5
3. 6, 5, 8, 7, 2, 4, 0 3. 8, 9, 8, 7
6, 5, 6, 7, 8
4. 2, 5, 8, 2, 6, 1, 1, 5, 3, 0 4. 10, 9, 9, 5
9, 10, 6, 8
5. 8, 7, 6, 1, 2, 3, 1, 1, 1, 0 5. 10, 10, 10
9, 6, 7, 8

You might also like