First Hellenic Internet Programming Contest
30 November 1996

Problem 2 - A Variation of Bin-packing

The bin-packing problem is well known from theory and practice. Given an infinite population of numbered bins, each of capacity 1, and a set of objects with weight smaller than 1, the problem is to find the minimum number of bins which can accommodate the set of objects. The exact solution may be found after exhaustive enumeration. Among the proposed suboptimal heuristics, the FIRST FIT DECREASING (FFD) method is a simple and efficient one. According to FFD, first we order the objects with decreasing weight, and then we place each object in the first bin which can accommodate it. We have to solve a variation of the classical bin-packing problem, where the bins have different capacities. Try to adapt the FFD algorithm in the new environment. Basically, you have to assign the objects (which are ordered decreasingly again) to the bins, which are also ordered according to decreasing capacity. If there are two or more objects with equal weight, or two or more bins with equal capacity, then in both cases we sort them according to their id's (i.e. order in the input). The key idea behind the proposed algorithm is that again the aim is to minimize the number of used bins. Therefore, it is better to use a few large bins instead of more small ones.

Input
Your program should read the INPUT2.TXT file, which has three lines.

• The first line contains the number of bins, b<=20, and the number of objects, o<=100.
• The second line contains b integers (in the range 1..10) representing the bin capacities.
• The third line contains o reals (in the range 0.1..9.9) representing the object weights.

Output
Output your results in the OUTPUT2.TXT file, which contains b lines. Each line corresponds to a bin (sorted in the order of the bins as given in the input file) and contains the object id's (sorted in the order of the objects as given in the input file), which are assigned to the specific bin. If a bin is not assigned any object, then the respective line contains a zero. Note, also, that the object id's in each line are separated by space characters.

Example 1

• Input
  4 5
  2 4 1 6
  0.5 2.5 3 1.2 0.8
  
• Output
  0
  4 5
  0
  1 2 3
  

Example 2

• Input
  4 5
  3 2 3 2
  0.5 1.5 1.5 2 0.5
  
• Output
  1 4 5
  0
  2 3
  0
  

In order to get the ASCII files of the problem click here.