Murtoreppuongelma: Ahne algoritmi esimerkin kanssa

Mikä on ahne strategia?

Ahneita algoritmeja pick the best local choice at each step in the hope that a chain of local optima produces a globally optimal solution. Like Dynamic Programming, they target optimization problems, but they never look back to reconsider earlier decisions.

Greedy algorithms are usually simple to write, fast (often linear or quadratic time), easy to debug, and light on memory. The trade-off is that the result is not always optimal, so the strategy only works for problems that have a proven greedy-safe structure.

Greedy strategies solve combinatorial optimization by building a solution A one component Ai at a time. At each step you pick Ai optimally under the current constraints and shrink the problem to a smaller subproblem.

Two properties must hold for a greedy method to be correct:

1. Greedy-choice property: a local optimum at each step leads to a global optimum. The choice depends on past decisions but not on future ones.
2. Optimal substructure: the optimal solution of the whole problem contains optimal solutions of its subproblems.

Ahneella algoritmilla on viisi osaa:

1. A candidate set from which solutions are built.
2. A selection function that picks the best next candidate.
3. A feasibility function that checks whether a candidate can extend the current partial solution.
4. An objective function that values a complete or partial solution.
5. An evaluation function that signals when the solution is complete.

Ahneen idea

Greedy One sorts packages by value alone:

• Sort packages in non-increasing order of value.
• Walk the sorted list and add each package to the knapsack if the remaining capacity can hold it.

This rule does not always give the optimal answer. Counter-example:

• Parameters: n = 3, M = 19.
• Packages: {i = 1; W = 14; V = 20}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 8} — high value but also high weight.
• Greedy One picks package 1 with total value 20, while the optimal choice (package 2, package 3) reaches 24.

Idea Greedy Twosta

Greedy Two sorts packages by weight alone:

• Sort packages in non-decreasing order of weight.
• Walk the sorted list and add each package to the knapsack if the remaining capacity can hold it.

This rule also fails to be optimal. Counter-example:

• Parameters: n = 3, M = 11.
• Packages: {i = 1; W = 5; V = 10}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 28} — light weight but low value.
• Greedy Two picks (package 1, package 2) with total value 26, while the optimal choice (package 3) reaches 28.

Ahneen Kolmon idea

Greedy Three fixes both failures by combining value and weight into a single ranking key. It is the standard method for the Fractional Knapsack Problem.

• Compute the unit cost V[i] / W[i] for every package.
• Sort packages in non-increasing order of unit cost.
• Walk the sorted list and add each package if the remaining capacity can hold it.

Greedy Three sorts by unit cost V[i] / W[i]

Idea: compute the value-to-weight ratio V[i] / W[i] for every package, sort in descending order, and take the largest available ratio first until the knapsack is full.

Totuuden puolesta murto- variant, when the next package cannot fit whole, take a fraction that exactly fills the remaining capacity. That extra rule is what makes Greedy Three provably optimal on Fractional Knapsack.

Steps of the Algorithm

For the 0/1 branch-and-bound variant, the sorted unit-cost list drives a search tree:

• Vaihe 1: The root node represents an empty knapsack. TotalValue = 0. UpperBound = M × maximum unit cost.
• Vaihe 2: Branch the root by how many copies of the largest-ratio package can fit. For every child, recompute TotalValue, remaining capacity M, and UpperBound.
• Vaihe 3: Expand the child with the largest UpperBound first, in the hope of finding a strong solution quickly.
• Vaihe 4: Prune any node whose UpperBound is no better than the current best complete solution.
• Vaihe 5: When every node is either expanded or pruned, the current best complete solution is optimal.

Pseudo code for the pure Fractional Knapsack greedy algorithm:

Fractional Knapsack (Array W, Array V, int M)
1. for i <- 1 to size(V)
2.     cost[i] <- V[i] / W[i]
3. Sort-Descending(cost)
4. total <- 0
5. i <- 1
6. while (i <= size(V) and M > 0)
7.     if W[i] <= M
8.         M <- M - W[i]
9.         total <- total + V[i]
10.        i <- i + 1
11.    else
12.        total <- total + V[i] * (M / W[i])
13.        M <- 0

Complexity of the algorithm:

• Using a simple sort (selection or bubble): O(n²).
• Using quick sort or merge sort: O(n log n), dominated by the sort step.

Java Code for Greedy Three

Määrittele KnapsackPackage class with weight, value, and derived cost (the V/W ratio used for sorting):

public class KnapsackPackage {

    private double weight;
    private double value;
    private Double cost;

    public KnapsackPackage(double weight, double value) {
        super();
        this.weight = weight;
        this.value = value;
        this.cost = Double.valueOf(value / weight);
    }

    public double getWeight() { return weight; }

    public double getValue() { return value; }

    public Double getCost()  { return cost; }
}

Then create the function that implements Greedy Three:

public void knapsackGreProc(int W[], int V[], int M, int n) {
    KnapsackPackage[] packs = new KnapsackPackage[n];
    for (int i = 0; i < n; i++) {
        packs[i] = new KnapsackPackage(W[i], V[i]);
    }

    Arrays.sort(packs, new Comparator<KnapsackPackage>() {
        @Override
        public int compare(KnapsackPackage a, KnapsackPackage b) {
            return b.getCost().compareTo(a.getCost());
        }
    });

    double remain = M;
    double result = 0d;

    for (int i = 0; i < n && remain > 0; i++) {
        if (packs[i].getWeight() <= remain) {
            remain -= packs[i].getWeight();
            result += packs[i].getValue();
            System.out.println("Pack " + i + " - Weight " + packs[i].getWeight()
                             + " - Value " + packs[i].getValue());
        } else {
            double fraction = remain / packs[i].getWeight();
            result += packs[i].getValue() * fraction;
            System.out.println("Pack " + i + " - Fraction " + fraction
                             + " - Value " + packs[i].getValue() * fraction);
            remain = 0;
        }
    }

    System.out.println("Max Value:\t" + result);
}

Funktio knapsackGreProc() in Java

Koodin selitys:

1. Wrap every input into a KnapsackPackage so the sort key (V/W ratio) is precomputed.
2. Sort in descending order of cost.
3. Take each package whole if it fits.
4. Take a fraction of the next package to fill the leftover capacity.
5. Stop as soon as remaining capacity reaches zero.

Fix note: Alkuperäisen Java loop advanced i only when a package did not fit, which caused the same package to be taken repeatedly. The version above advances one package per iteration and adds a fractional-fill step, matching the true Fractional Knapsack rule.

Java driver that runs the algorithm on a worked example:

public void run() {
    int W[] = new int[]{15, 10, 2, 4};
    int V[] = new int[]{30, 25, 2, 6};
    int M = 37;
    int n = V.length;
    knapsackGreProc(W, V, M, n);
}

Python3 Code for Greedy Three

First define the KnapsackPackage luokassa. __lt__ method makes it directly sortable by cost:

class KnapsackPackage(object):
    """Knapsack Package Data Class"""

    def __init__(self, weight, value):
        self.weight = weight
        self.value  = value
        self.cost   = value / weight

    def __lt__(self, other):
        return self.cost < other.cost

Then implement the Fractional Knapsack routine:

class FractionalKnapsack(object):

    def knapsackGreProc(self, W, V, M, n):
        packs = [KnapsackPackage(W[i], V[i]) for i in range(n)]
        packs.sort(reverse=True)

        remain = M
        result = 0

        for i in range(n):
            if remain == 0:
                break
            if packs[i].weight <= remain:
                remain -= packs[i].weight
                result += packs[i].value
                print("Pack", i, "- Weight", packs[i].weight, "- Value", packs[i].value)
            else:
                fraction = remain / packs[i].weight
                result += packs[i].value * fraction
                print("Pack", i, "- Fraction", fraction,
                      "- Value", packs[i].value * fraction)
                remain = 0

        print("Max Value:", result)

Funktio knapsackGreProc() in Python

Fix note: Alkuperäisen Python class defined an empty __init__ with no body, which raises IndentationError. The version above removes the empty constructor because none is needed.

Driver that runs the algorithm on the first example:

if __name__ == "__main__":
    W = [15, 10, 2, 4]
    V = [30, 25, 2, 6]
    M = 37
    n = 4

    proc = FractionalKnapsack()
    proc.knapsackGreProc(W, V, M, n)

C# Code for Greedy Three

Määrittele KnapsackPackage luokka:

using System;

namespace KnapsackProblem
{
    public class KnapsackPackage
    {
        private double weight;
        private double value;
        private double cost;

        public KnapsackPackage(double weight, double value)
        {
            this.weight = weight;
            this.value  = value;
            this.cost   = value / weight;
        }

        public double Weight { get { return weight; } }
        public double Value  { get { return value; } }
        public double Cost   { get { return cost; } }
    }
}

Implement Greedy Three with a fractional-fill step:

public void KnapsackGreProc(int[] W, int[] V, int M, int n)
{
    KnapsackPackage[] packs = new KnapsackPackage[n];
    for (int k = 0; k < n; k++)
        packs[k] = new KnapsackPackage(W[k], V[k]);

    Array.Sort<KnapsackPackage>(packs,
        (a, b) => b.Cost.CompareTo(a.Cost));

    double remain = M;
    double result = 0d;

    for (int i = 0; i < n && remain > 0; i++)
    {
        if (packs[i].Weight <= remain)
        {
            remain -= packs[i].Weight;
            result += packs[i].Value;
            Console.WriteLine("Pack " + i + " - Weight " + packs[i].Weight
                            + " - Value " + packs[i].Value);
        }
        else
        {
            double fraction = remain / packs[i].Weight;
            result += packs[i].Value * fraction;
            Console.WriteLine("Pack " + i + " - Fraction " + fraction
                            + " - Value " + packs[i].Value * fraction);
            remain = 0;
        }
    }

    Console.WriteLine("Max Value:\t" + result);
}

Funktio KnapsackGreProc() C#:ssa

Counter-Example: Greedy Three on 0/1 Knapsack

Greedy Three is optimal for the Fractional variant, but on the 0/1 Knapsack (where items cannot be split) it can be beaten. Counter-example:

• Parameters: n = 3, M = 10.
• Packages: {i = 1; W = 7; V = 9; cost = 9/7}, {i = 2; W = 6; V = 6; cost = 1}, {i = 3; W = 4; V = 4; cost = 1}.
• Greedy Three picks package 1 for total value 9, while the optimal 0/1 choice (package 2, package 3) reaches 10.

The lesson: use Greedy Three only when fractions are allowed. For the 0/1 variant, use Dynaaminen ohjelmointi sen sijaan.

Applications of Fractional Knapsack

• Cargo loading where liquid, powdered, or bulk goods can be split by weight.
• Portfolio allocation across investment options that accept partial funding.
• Cloud bandwidth sharing where flows can consume a fraction of a link.
• CPU scheduling under a shared-time-slice model with divisible workloads.
• AI resource allocation where a training job can use a fraction of a GPU.

UKK