java实现贪心算法背包问题

一般背包问题是指物品可以分割，也就是说允许将物品的一部分装进背包。下面是Java实现贪心算法解决一般背包问题的步骤：

1. 定义一个物品类Item，包含物品的重量和价值两个属性。
2. 定义一个比较器类ItemComparator，用于按照单位重量的价值从大到小排序。
3. 定义一个贪心算法的方法，输入参数为背包容量和物品数组，输出为背包能够装下的最大价值。
4. 在贪心算法中，首先按照单位重量的价值从大到小对物品数组进行排序。
5. 然后依次将物品放入背包中，直到背包装满为止。

下面是Java代码实现：

class Item {
    int weight;
    int value;
    public Item(int weight, int value) {
        this.weight = weight;
        this.value = value;
    }
}

class ItemComparator implements Comparator<Item> {
    public int compare(Item a, Item b) {
        double r1 = (double) a.value / a.weight;
        double r2 = (double) b.value / b.weight;
        if (r1 > r2) {
            return -1;
        } else if (r1 < r2) {
            return 1;
        } else {
            return 0;
        }
    }
}

public class Knapsack {
    public static int knapsack(int W, Item[] items) {
        Arrays.sort(items, new ItemComparator());
        int value = 0;
        int weight = 0;
        for (Item item : items) {
            if (weight + item.weight <= W) {
                value += item.value;
                weight += item.weight;
            } else {
                int remain = W - weight;
                value += remain * item.value / item.weight;
                break;
            }
        }
        return value;
    }
}