用java编写贪心算法求背包问题

以下是使用Java编写贪心算法求解背包问题的示例代码：

import java.util.Arrays;

public class Knapsack {

    static class Item implements Comparable<Item> {
        int weight;
        int value;
        double ratio;

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

        @Override
        public int compareTo(Item o) {
            if (o == null) {
                return -1;
            }
            return Double.compare(o.ratio, ratio);
        }
    }

    public static int knapsack(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        Item[] items = new Item[n];
        for (int i = 0; i < n; i++) {
            items[i] = new Item(weights[i], values[i]);
        }
        Arrays.sort(items);

        int result = 0;
        for (int i = 0; i < n; i++) {
            if (items[i].weight <= capacity) {
                result += items[i].value;
                capacity -= items[i].weight;
            } else {
                result += items[i].ratio * capacity;
                break;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] weights = {10, 20, 30};
        int[] values = {60, 100, 120};
        int capacity = 50;
        System.out.println(knapsack(weights, values, capacity));
    }
}

在这个示例中，我们首先定义了一个`Item`类，用于存储物品的重量、价值和价值重量比。我们还实现了`Comparable`接口，以便我们可以按照价值重量比对物品进行排序。

接下来，我们将物品按照价值重量比进行排序，并遍历物品，将能够放入背包的物品加入背包。如果一个物品无法完全放入背包中，则将其部分放入背包，以使背包容量完全用尽。

最后，我们返回所有物品的总价值，这就是我们使用贪心算法求解背包问题的结果。