Greedy Algorithm for the Knapsack Problem with Java Implementation

The article introduces a knapsack problem where a backpack of capacity 10 can hold a set of items, each with a specific weight and value, and explains how to calculate each item's value‑to‑weight ratio (性价比) to guide selection.

Using the greedy strategy, items are sorted in descending order of their ratios, and the algorithm picks the highest‑ratio items that fit, possibly taking a fractional part of the last item if the remaining capacity is insufficient for a whole item.

An example is shown where the algorithm first selects item 4 (ratio highest), then item 1, and finally a fractional part of item 5, achieving a total value of 15.5. A second scenario with a restriction that items must be taken whole demonstrates that greedy selection can be sub‑optimal (value 6 vs. optimal value 7).

The full Java code implementing this greedy knapsack solution is provided below:

public static void main(String[] args) {
    int capacity = 10;
    int[] weights = {4,6,3,2,5};
    int[] values = {9,3,1,6,5};
    System.out.println("背包最大价值：" + getHighestValue(capacity, weights, values));
}

public static double getHighestValue(int capacity, int[] weights, int[] values) {
    // Create item list and sort by ratio descending
    List
itemList = new ArrayList<>();
    for (int i = 0; i < weights.length; i++) {
        itemList.add(new Item(weights[i], values[i]));
    }
    itemList = itemList.stream()
        .sorted(Comparator.comparing(Item::getRatio).reversed())
        .collect(Collectors.toList());

    int restCapacity = capacity;
    double highestValue = 0;

    // Greedy selection based on ratio
    for (Item item : itemList) {
        if (item.weight <= restCapacity) {
            highestValue += item.value;
            restCapacity -= item.weight;
        } else {
            // Take fractional part if full item doesn't fit
            highestValue += (double) restCapacity / (double) item.weight * item.value;
            break;
        }
    }
    return highestValue;
}

static class Item {
    private int weight;
    private int value;
    private double ratio; // value-to-weight ratio

    public Item(int weight, int value) {
        this.weight = weight;
        this.value = value;
        this.ratio = (double) value / (double) weight;
    }

    public double getRatio() {
        return ratio;
    }
}

The article concludes by highlighting that while the greedy method is simple and fast, it does not guarantee the optimal solution for the 0/1 knapsack problem, prompting the need for more exhaustive approaches such as dynamic programming.