Greedy Method: Knapsack, Job Sequencing, and Optimal Storage

The Greedy Method is a straightforward algorithmic paradigm often used for optimization problems. It builds a solution piece by piece, making the choice that looks best at the moment, with the hope that this local optimum will lead to a global optimum. This approach is particularly effective for problems exhibiting two key properties: optimal substructure and the greedy choice property.

1. The Greedy Method: Core Principles

The general method of greedy algorithms involves making a sequence of choices. At each stage, the algorithm considers a specific input and makes a decision whether to include it in the solution or not. This decision is based on some predefined selection procedure or greedy criterion, which aims to maximize or minimize a certain objective function.

Feasible Solution: Any subset of inputs that satisfies the problem's constraints.
Optimal Solution: A feasible solution that either maximizes or minimizes the objective function.

A greedy algorithm proceeds in stages, making decisions that are:

Locally Optimal: At each step, it chooses the option that appears best right now.
Irreversible: Once a choice is made, it cannot be undone.

For a greedy algorithm to guarantee an optimal solution, the problem must exhibit:

Optimal Substructure: An optimal solution to the problem contains optimal solutions to subproblems.
Greedy Choice Property: A globally optimal solution can be reached by making a locally optimal (greedy) choice at each stage. That is, the best choice available at the moment will extend to an optimal solution for the larger problem.

Not all optimization problems can be solved optimally using a greedy approach. It's crucial to verify these properties for a given problem.

2. Fractional Knapsack Problem

The Fractional Knapsack Problem is a classic optimization problem where the goal is to fill a knapsack with items to maximize the total profit, given that the knapsack has a maximum weight capacity. Unlike the 0/1 Knapsack problem, items can be broken into fractions.

Problem Statement: Given $n$ objects, each with a profit $P_i$ and a weight $W_i$ , and a knapsack with a capacity $M$ . If a fraction $X_i$ of object is placed in the knapsack, a profit is earned, and a weight is consumed. The objective is to maximize the total profit: Subject to:

Greedy Strategy: The optimal greedy strategy for the Fractional Knapsack Problem is to prioritize items based on their profit-per-unit-weight ratio ( $P_i/W_i$ ).

Calculate $P_i/W_i$ for all items.
Sort items in descending order of their $P_i/W_i$ ratio.

Example: Let $n=3$ , capacity $M=20$ . Items: $(P_1, W_1)=(25, 18)$ , , .

Calculate Ratios ( $P_i/W_i$ ):
- Item 1: $25/18 \approx 1.389$
- Item 2: $24/15 = 1.6$

Optimal Solution: Take Item 2 entirely, and half of Item 3. Total profit = $31.5$ .

C++ Code Example: Fractional Knapsack

cpp

#include <iostream>
#include <vector>
#include <algorithm> // For std::sort
 
// Structure to represent an item
struct Item {
    int profit;
    int weight;
    double ratio; // profit/weight ratio
 
    // Constructor
    Item(int p, int w) : profit(p), weight(w) {
        ratio = static_cast<double>(profit) / weight;
    }
};
 
// Custom comparison function for sorting items by ratio in descending order
bool compareItems(const Item& a, const Item& b) {
    return a.ratio > b.ratio;

3. Job Sequencing with Deadlines

The Job Sequencing with Deadlines problem aims to find a sequence of jobs, each with a profit and a deadline, to maximize the total profit. There is only one machine available, and each job takes one unit of time to complete.

Problem Statement: Given a set of $n$ jobs $J = \{J_1, J_2, \dots, J_n\}$ . Each job has an associated profit and an integer deadline . A job is completed by its deadline if it starts at time and finishes by time . Only one job can be processed at a time. The objective is to find a subset of jobs that can be completed by their deadlines and yields the maximum total profit.

Greedy Strategy: The greedy approach for Job Sequencing with Deadlines is as follows:

Sort all jobs in descending order of their profits.
Initialize an empty schedule (e.g., an array schedule[max_deadline], where max_deadline is the largest deadline among all jobs).
Iterate through the sorted jobs:
- For each job, try to schedule it in the latest possible available time slot before or at its deadline.
- If a job $J_i$ has deadline $D_i$ , try to place it at time slot $D_i-1$ . If that slot is taken, try , and so on, until an empty slot is found or time is reached.

Example: Let $n=5$ jobs. | Job | Deadline ( $D_i$ ) | Profit ( $P_i$ ) | | :-- | :--------------- | :------------- | | J1 | 2 | 20 | | J2 | 2 | 60 | | J3 | 1 | 40 | | J4 | 3 | 100 | | J5 | 4 | 80 |

Sort by Profit (descending):
- J4 ( $P=100, D=3$ )
- J5 ( $P=80, D=4$ )
- J2 ( $P=60, D=2$ )

Optimal Schedule: Total Profit: $40 + 60 + 100 + 80 = 280$ .

Visualizing the schedule:

text

Time Slot:  0-1  1-2  2-3  3-4
Job:       J3   J2   J4   J5

4. Optimal Storage on Tapes

The Optimal Storage on Tapes problem deals with arranging programs on a single tape to minimize the mean retrieval time (MRT). When a program is to be retrieved, the tape is positioned at the front, and the tape head scans forward until the desired program is found.

Problem Statement: Given $n$ programs $I_1, I_2, \dots, I_n$ with lengths . These programs are to be stored on a computer tape. When a program is retrieved, the tape must scan through all programs stored before , including itself. The objective is to find an optimal permutation (order) of these programs on the tape that minimizes the .

If programs are stored in the order $I_{(1)}, I_{(2)}, \dots, I_{(n)}$ , where is the -th program in the sequence, the time required to retrieve is .

The Mean Retrieval Time (MRT) is calculated as: $MRT = \frac{1}{n} \sum_{k=1}^{n} \left( \sum_{j=1}^{k} L_{(j)} \right)$

Greedy Strategy: To minimize the MRT, the greedy strategy is straightforward:

Sort all programs in ascending order of their lengths.
Store the programs on the tape in this sorted order.

Why this works: Placing shorter programs first minimizes the cumulative length that needs to be scanned for subsequent programs. This reduction in scan time for many programs at the beginning of the tape has a greater impact on the total retrieval time than placing longer programs early.

Example: Let $n=3$ programs with lengths: $L_1=5, L_2=10, L_3=3$ .

Sort by Length (ascending):
- Program 3 ( $L=3$ )
- Program 1 ( $L=5$ )
- Program 2 ( $L=10$ )
Optimal Storage Order: $(I_3, I_1, I_2)$

The greedy choice (shortest program first) clearly yields a smaller MRT.

text

Tape Layout:
+-----+-----+--------+
| P3  | P1  | P2     |
| (3) | (5) | (10)   |
+-----+-----+--------+
0     3     8        18 (Total length)
 
Retrieval Sequence:
1. P3: Scan 3 units
2. P1: Scan 3+5 = 8 units
3. P2: Scan 3+5+10 = 18 units
 
Sum of Retrieval Times = 3 + 8 + 18 = 29
Mean Retrieval Time = 29 / 3 approx 9.67

5. When Does Greedy Work? (Limitations)

While powerful, the greedy method isn't universally applicable. Its success hinges on the greedy choice property and optimal substructure. Problems like the 0/1 Knapsack Problem, where items cannot be fractioned, do not satisfy the greedy choice property; a locally optimal choice (e.g., taking an item with the highest profit/weight ratio) might prevent a better overall solution later. For such problems, dynamic programming or other methods are often required.

Other greedy applications not covered in detail here but often mentioned:

Optimal Merge Pattern: Merging sorted files to minimize total comparisons, solved by repeatedly merging the two smallest files.
Huffman Coding: Constructing a prefix code to represent characters with variable lengths based on their frequencies, minimizing the total encoded message length.

Summary

The Greedy Method builds solutions incrementally by making locally optimal choices at each stage.
It works effectively for problems exhibiting optimal substructure and the greedy choice property.
In the Fractional Knapsack Problem, the greedy strategy is to select items based on their highest profit-per-unit-weight ratio ( $P_i/W_i$ ).
For Job Sequencing with Deadlines, jobs are prioritized by highest profit and scheduled into the latest possible available time slot by their deadline.
To achieve Optimal Storage on Tapes (minimizing Mean Retrieval Time), programs should be arranged in ascending order of their lengths.
The greedy method is not suitable for all optimization problems, notably those where local optimal choices do not guarantee a global optimum (e.g., the 0/1 Knapsack Problem).

Assessed progress

Greedy Method: Knapsack, Job Sequencing, and Optimal Storage

Greedy Method: Knapsack, Job Sequencing, and Optimal Storage

1. The Greedy Method: Core Principles

2. Fractional Knapsack Problem

C++ Code Example: Fractional Knapsack

3. Job Sequencing with Deadlines

4. Optimal Storage on Tapes

5. When Does Greedy Work? (Limitations)

Summary

Key Concepts

Greedy Choice Property

Optimal Substructure

Fractional Knapsack Problem

Job Sequencing with Deadlines

Optimal Storage on Tapes

Quick Check

Advanced Data Structures

Advanced Data Structures