背包问题的贪心算法实现（Java）

背包问题是一经典的组合优化问题,贪心算法是解决该问题的一种方法，下面我将介绍背包问题的两种主要类型（0/1背包和分数背包）及其贪心算法的Java实现。

分数背包问题（Fractional Knapsack）

分数背包问题允许物品被分割,我们可以选择物品的一部分放入背包。

贪心策略

按物品的单位重量价值（价值/重量）降序排列，优先选择单位价值最高的物品。

Java实现

import java.util.Arrays;
import java.util.Comparator;
class Item {
    int weight;
    int value;
    public Item(int weight, int value) {
        this.weight = weight;
        this.value = value;
    }
}
public class FractionalKnapsack {
    // 计算背包能获得的最大价值
    public static double getMaxValue(Item[] items, int capacity) {
        // 按单位重量价值降序排序
        Arrays.sort(items, new Comparator<Item>() {
            @Override
            public int compare(Item a, Item b) {
                double r1 = (double)a.value / a.weight;
                double r2 = (double)b.value / b.weight;
                return Double.compare(r2, r1); // 降序
            }
        });
        double totalValue = 0.0;
        int currentWeight = 0;
        for (Item item : items) {
            if (currentWeight + item.weight <= capacity) {
                // 可以放入整个物品
                currentWeight += item.weight;
                totalValue += item.value;
            } else {
                // 放入物品的一部分
                int remaining = capacity - currentWeight;
                totalValue += item.value * ((double)remaining / item.weight);
                break;
            }
        }
        return totalValue;
    }
    public static void main(String[] args) {
        Item[] items = {
            new Item(10, 60),    // 价值6/重量
            new Item(20, 100),   // 价值5/重量
            new Item(30, 120)    // 价值4/重量
        };
        int capacity = 50;
        double maxValue = getMaxValue(items, capacity);
        System.out.println("最大价值: " + maxValue);
    }
}

0/1背包问题（0/1 Knapsack）

0/1背包问题不允许物品被分割，每个物品要么整个放入背包，要么不放入。

贪心策略

对于0/1背包问题，贪心算法不能保证得到最优解，但可以得到一个近似解，常见的贪心策略有：

1. 按价值降序
2. 按重量升序
3. 按单位价值降序

Java实现（按单位价值降序的贪心算法）

import java.util.Arrays;
import java.util.Comparator;
class Item {
    int weight;
    int value;
    public Item(int weight, int value) {
        this.weight = weight;
        this.value = value;
    }
}
public class ZeroOneKnapsackGreedy {
    // 计算背包能获得的最大价值（贪心算法，不保证最优解）
    public static int getMaxValue(Item[] items, int capacity) {
        // 按单位重量价值降序排序
        Arrays.sort(items, new Comparator<Item>() {
            @Override
            public int compare(Item a, Item b) {
                double r1 = (double)a.value / a.weight;
                double r2 = (double)b.value / b.weight;
                return Double.compare(r2, r1); // 降序
            }
        });
        int totalValue = 0;
        int currentWeight = 0;
        for (Item item : items) {
            if (currentWeight + item.weight <= capacity) {
                // 可以放入整个物品
                currentWeight += item.weight;
                totalValue += item.value;
            }
            // 否则跳过该物品
        }
        return totalValue;
    }
    public static void main(String[] args) {
        Item[] items = {
            new Item(10, 60),    // 价值6/重量
            new Item(20, 100),   // 价值5/重量
            new Item(30, 120)    // 价值4/重量
        };
        int capacity = 50;
        int maxValue = getMaxValue(items, capacity);
        System.out.println("最大价值（贪心算法）: " + maxValue);
        // 对于0/1背包问题，动态规划能得到最优解
        System.out.println("最大价值（动态规划最优解）: " + knapSack(capacity, items.length, items));
    }
    // 动态规划解法（最优解）
    private static int knapSack(int W, int n, Item[] items) {
        int i, w;
        int[][] K = new int[n + 1][W + 1];
        for (i = 0; i <= n; i++) {
            for (w = 0; w <= W; w++) {
                if (i == 0 || w == 0)
                    K[i][w] = 0;
                else if (items[i - 1].weight <= w)
                    K[i][w] = Math.max(items[i - 1].value + K[i - 1][w - items[i - 1].weight], K[i - 1][w]);
                else
                    K[i][w] = K[i - 1][w];
            }
        }
        return K[n][W];
    }
}

注意事项

1. 分数背包问题：贪心算法可以保证得到最优解
2. 0/1背包问题：贪心算法不能保证得到最优解，只能得到近似解，要得到最优解需要使用动态规划
3. 贪心算法的关键在于选择合适的贪心策略,对于不同的问题可能需要不同的策略

希望这些实现能帮助你理解背包问题的贪心算法解决方法！