50089. Buckets and Balls, Again

I'm a slow walker, but I never walk backwards.

Task Description

Place balls into buckets according to first fit, best fit, and worst fit.

We are given $N$ buckets with index from 0 to $N-1$ and $M$ balls. Each bucket has a weight limit and each ball has a weight. Now we need to put the balls one by one into buckets, and we should make sure that the total weight of balls in a bucket does not exceed the weight limit. Once we put a ball into a bucket, we record the bucket index. If we could not find a bucket for a ball because it is too heavy, then we discard the ball and record -1. Write a function to record the how we place balls into buckets.

The balls can be put into the bucket according to either of the following three rules.

First fit. We place the ball to the first bucket that can hold it. If no bucket can hold the ball, we discard it.

Best fit. We place the ball into the bucket that has the smallest remaining capacity after placing the ball. If no bucket can hold this ball, we discard the ball. Note that if more than one buckets have the same smallest remaining capacity, we put the ball into the one with the smallest index.

Worst fit. We place the ball into the bucket that has the largest remaining capacity after placing the ball. If no bucket can hold this ball, we discard the ball. Note that if more than one buckets have the same largest remaining capacity, we put the ball into the one with the largest index.

We use an example to illustrate the placement. Now we have three buckets ($b0$, $b1$, and $b2$), and four balls. The weight limits of the buckets are {13, 11, 12}, and the weights of the four balls are {7, 8, 4, 9}.

When we use first fit, the following will happen.

  • Iteration 1: we put the first ball of weight 7 into $b0$ because $b0$ has room for it, and the remaining capacity sequence is {6, 11, 12}.
  • Iteration 2: we put the second ball of weight 8 into $b1$ because $b1$ has enough room and the index is the smallest. The remaining capacity sequence is {6, 3, 12}.
  • Iteration 3: we put the third ball of weight 4 into $b0$ because $b0$ has enough room and the remaining capacity sequence is {2, 3, 12}.
  • Iteration 4: we put the fourth ball of weight 9 into $b2$ because $b2$ is the only bucket with enough capacity.

The buckets the balls go to are {0, 1, 0, 2}.

When we use best fit the following will happen.

  • Iteration 1: we put the first ball of weight 7 into $b1$ because $b1$ has the smallest remaining capacity, and the remaining capacity sequence is {13, 4, 12}.
  • Iteration 2: we put the second ball of weight 8 into $b2$ because $b2$ has the smallest remaining capacity, and the remaining capacity sequence is {13, 4, 4}.
  • Iteration 3: we put the third ball of weight 4 into $b1$ because $b1$ has smallest remaining capacity and the index is the smallest. The remaining capacity sequence is {13, 0, 4}.
  • Iteration 4: we put the fourth ball of weight 9 into $b0$ because b0 is the only bucket with enough capacity.

The buckets the balls go to are {1, 2, 1, 0}.

When we use worst fit:

  • Iteration 1: we put the first ball of weight 7 into $b0$ because $b0$ has the largest remaining capacity, and the remaining capacity sequence is {6, 11, 12}.
  • Iteration 2: we put the second ball of weight 8 into $b2$ because $b2$ has the largest remaining capacity, and the remaining capacity sequence is {6, 11, 4}.
  • Iteration 3: we put the third ball of weight 4 into $b1$ because $b1$ has the largest remaining capacity, and the remaining capacity sequence is {6, 7, 4}.
  • Iteration 4: we discard the fourth ball of weight 9 because there is no bucket with enough capacity, and we record -1.

The buckets the balls go to are {0, 2, 1, -1}.

You may use the following main function to test your function.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<stdio.h>
#include"placement.h"
 
int main(){
    int N,M,method;
    scanf("%d%d%d",&N,&M,&method);
    int buckets[N];
    for(int i=0;i<N;i++)
        scanf("%d",&buckets[i]);
    int balls[M];
    for(int i=0;i<M;i++)
        scanf("%d",&balls[i]);
    int result[M];
    place(buckets,N,balls,M,method,result);
    for(int i=0;i<M;i++)
        printf("%d%s",result[i],i==M-1?"":" ");
    return 0;
}

The prototype of place function is as follows.

1
void place(int bucket[1024],int N,int ball[16384],int M,int method,int result[16384]);

The placement.h is as follow:

1
void place(int bucket[1024],int N,int ball[16384],int M,int method,int result[16384]);

Subtask

  • 20 points: Implement the first fit.
  • 40 points: Implement the best fit.
  • 40 points: Implement the worst fit.

Input Format

The input contains only one test case. The first line contains three integers $N$, $M$, and an integer for the placement method, where $N$ is the bucket number, $M$ is the ball number.

  • When the method is 0, we use first fit.
  • When the method is 1, we use best fit.
  • When the method is 2, we use worst fit.

The second line contains $N$ integers, and the $i-th$ integer represents the weight limit of bucket bi. The third line contains $M$ integers, and each integer represents the weight of a ball.

  • $N \leq 1024.$
  • $M \leq 16384.$

Output Format

Print the buckets the balls go to in a line. If we discard a ball, the placement of the ball is -1.

Sample Input 1

3 4 0
13 11 12
7 8 4 9

Sample Output 1

0 1 0 2

Sample Input 2

3 4 1
13 11 12
7 8 4 9

Sample Output 2

1 2 1 0

Sample Input 3

3 4 2
13 11 12
7 8 4 9

Sample Output 3

0 2 1 -1

Compile

gcc -std=c99 -O2 -c main.c -lm
gcc -std=c99 -O2 -c placement.c -lm
gcc -std=c99 -O2 placement.o main.o -lm

Discussion