ISC Practicals and Theory - Carton Packing

A company packs articles in cartons of four sizes: 48, 24, 12 and 6 articles. Given the number of articles, the program finds how many cartons of each size are used, the total number of cartons and the articles that are left over. This version is the straightforward one: everything is written in the main method.

Definition

Greedy packing means taking the largest carton first: use as many cartons of 48 as possible, then as many of 24 as possible from what is left, then 12, then 6. The articles still left after the cartons of 6 (fewer than 6) are the remaining articles and are not packed.

With integer division, the number of cartons of size $s$ for $x$ articles is x / s and the articles left are x % s.

For example, for 143 articles: $143 = 2 \times 48 + 47$, then $47 = 1 \times 24 + 23$, then $23 = 1 \times 12 + 11$, then $11 = 1 \times 6 + 5$. So there are 2, 1, 1 and 1 cartons (5 in all) and 5 articles remain.

Algorithm

1. Read the number of articles n. If it is not from 1 to 1000000, print INVALID INPUT and stop.
2. Store the carton sizes, largest first, in the array size: 48, 24, 12 and 6. The array count will hold the number of cartons of each size.
3. Set left = n, the articles not yet packed. For each size in turn, count[i] = left / size[i] is the number of whole cartons of that size, and left = left % size[i] is what is still to be packed.
4. After the last size, left is the number of articles left over (fewer than 6), which cannot be packed.
5. Print the number of cartons of each size, add them up for the total, and print the total and the remaining articles.

Program

Everything is written inside main: the first for loop packs the cartons from the largest size down, and the second prints the counts and adds them up.

import java.util.Scanner;
public class Carton
{
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter the number of articles: ");
        int n = sc.nextInt();                  // number of articles to be packed
        if (n < 1 || n > 1000000)
        {
            System.out.println("INVALID INPUT");
        }
        else
        {
            int size[] = {48, 24, 12, 6};      // carton sizes, largest first
            int count[] = new int[4];          // count[i] = number of cartons of size[i] used
            int left = n;                      // articles not yet packed
            for (int i = 0; i < 4; i++)
            {
                count[i] = left / size[i];     // whole cartons of this size
                left = left % size[i];         // articles still to be packed
            }
            int total = 0;                     // total number of cartons used
            for (int i = 0; i < 4; i++)
            {
                System.out.println("Cartons of " + size[i] + ": " + count[i]);
                total = total + count[i];
            }
            System.out.println("Total cartons: " + total);
            System.out.println("REMAINING articles: " + left);   // fewer than 6, not packed
        }
    }
}

Variable description table

Sample input and output

Enter the number of articles: 143
Cartons of 48: 2
Cartons of 24: 1
Cartons of 12: 1
Cartons of 6: 1
Total cartons: 5
REMAINING articles: 5

Enter the number of articles: 48
Cartons of 48: 1
Cartons of 24: 0
Cartons of 12: 0
Cartons of 6: 0
Total cartons: 1
REMAINING articles: 0

Enter the number of articles: 59
Cartons of 48: 1
Cartons of 24: 0
Cartons of 12: 0
Cartons of 6: 1
Total cartons: 2
REMAINING articles: 5

Enter the number of articles: 5
Cartons of 48: 0
Cartons of 24: 0
Cartons of 12: 0
Cartons of 6: 0
Total cartons: 0
REMAINING articles: 5

Enter the number of articles: 30
Cartons of 48: 0
Cartons of 24: 1
Cartons of 12: 0
Cartons of 6: 1
Total cartons: 2
REMAINING articles: 0

Enter the number of articles: 1000000
Cartons of 48: 20833
Cartons of 24: 0
Cartons of 12: 1
Cartons of 6: 0
Total cartons: 20834
REMAINING articles: 4

Enter the number of articles: 0
INVALID INPUT

Enter the number of articles: 1000001
INVALID INPUT

Dry run

Take the input $n = 143$. left starts as 143.

After the loop left = 5, the articles left over. The total is $2 + 1 + 1 + 1 = 5$. The program prints 2, 1, 1 and 1 cartons, Total cartons: 5 and REMAINING articles: 5, as in the first sample run.

Variations

1. Currency notes "Read an amount and find the smallest number of notes of each denomination needed to make it." This uses the same / and % idea.
2. Sizes read from the user "Read the carton sizes in descending order and pack the articles in the same way."