贪心算法01背包问题设计java代码实现

以下是使用Java语言实现01背包问题的贪心算法代码：

import java.util.Arrays;
import java.util.Comparator;

public class Knapsack {
    // 定义物品类，包含重量和价值两个属性
    static class Item {
        int weight;
        int value;
        double unitValue;

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

    // 贪心算法实现
    public static int knapsack(int W, int[] wt, int[] val) {
        int n = wt.length;
        Item[] items = new Item[n];
        for (int i = 0; i < n; i++) {
            items[i] = new Item(wt[i], val[i]);
        }
        // 按照单位重量价值进行排序
        Arrays.sort(items, Comparator.comparingDouble(o -> -o.unitValue));
        // 初始化背包容量和价值
        int maxVal = 0, remWeight = W;
        // 依次将单位重量价值最高的物品放入背包
        for (int i = 0; i < n; i++) {
            if (items[i].weight <= remWeight) {
                maxVal += items[i].value;
                remWeight -= items[i].weight;
            } else {
                maxVal += items[i].unitValue * remWeight;
                break;
            }
        }
        return maxVal;
    }

    public static void main(String[] args) {
        int W = 50;
        int[] val = {60, 100, 120};
        int[] wt = {10, 20, 30};
        System.out.println(knapsack(W, wt, val)); // 240
    }
}

在实现中，我们定义了一个物品类，包含了物品的重量、价值和单位重量价值三个属性。然后将物品按照单位重量价值从大到小排序，依次将单位重量价值最高的物品放入背包中，直到背包装满或者所有物品都已经放入背包中为止。