Java贪心珠宝盗窃算法：读取文件后分配重量与值的实现问题

嘿，看起来你已经搞定了文件读取的部分，就差把那些重量-价值对转成程序能处理的数据结构了对吧？别担心，我来给你一步步捋清楚怎么做。

首先咱们先明确你的文件格式：

575 - 背包容量（bag limit）；
125 3000（重量，价值）；
50 100；
500 6000；
25 30；

这种情况下，自定义一个物品类是最适合的方案——比起普通的键值对（比如Map），自定义类能清晰关联每个珠宝的重量和价值，还能避免相同重量珠宝的数据覆盖问题，同时方便后续贪心算法计算单位价值。

步骤1：创建Item类封装珠宝信息 #

先写一个简单的Item类，把重量、价值打包在一起，再加上贪心算法需要的单位价值计算方法：

public class Item {
    private int weight;
    private int value;

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

    // 计算单位重量价值，贪心排序的核心依据
    public double getValuePerWeight() {
        return (double) value / weight;
    }

    // 基础getter方法，方便后续获取数据
    public int getWeight() {
        return weight;
    }

    public int getValue() {
        return value;
    }
}

步骤2：解析文件数据，生成Item列表 #

接下来把你已有的文件读取逻辑和解析逻辑结合，把每行的重量-价值对转换成Item对象，存入列表中：

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;

public class GreedyJewelryThief {
    public static void main(String[] args) {
        String filePath = "你的珠宝数据文件路径.txt";
        int bagLimit = 0;
        List<Item> items = new ArrayList<>();

        try (BufferedReader br = new BufferedReader(new FileReader(filePath))) {
            // 读取第一行的背包容量
            String line = br.readLine();
            if (line != null) {
                // 去掉注释部分，只提取数字
                bagLimit = Integer.parseInt(line.split("-")[0].trim());
            }

            // 读取后续所有珠宝数据行
            while ((line = br.readLine()) != null) {
                // 清理行尾的分号，按空格分割成重量和价值
                String[] parts = line.replace(";", "").trim().split("\\s+");
                if (parts.length == 2) {
                    int weight = Integer.parseInt(parts[0]);
                    int value = Integer.parseInt(parts[1]);
                    items.add(new Item(weight, value));
                }
            }

        } catch (IOException e) {
            System.out.println("读取文件时出错啦：");
            e.printStackTrace();
        } catch (NumberFormatException e) {
            System.out.println("文件数据格式不对哦，请检查重量和价值是不是整数：");
            e.printStackTrace();
        }

        // 测试输出，确认数据解析正确
        System.out.println("背包容量：" + bagLimit);
        System.out.println("已解析的珠宝列表：");
        for (Item item : items) {
            System.out.printf("重量：%d，价值：%d，单位价值：%.2f%n",
                    item.getWeight(), item.getValue(), item.getValuePerWeight());
        }
    }
}

步骤3：贪心算法核心逻辑（可选补充） #

拿到items列表后，只需要按单位重量价值从高到低排序，然后依次选取物品直到背包填满即可：

import java.util.Collections;
import java.util.Comparator;

// 在main方法里添加这段排序和贪心选择逻辑
Collections.sort(items, new Comparator<Item>() {
    @Override
    public int compare(Item o1, Item o2) {
        // 降序排序，让单位价值高的珠宝先被选中
        return Double.compare(o2.getValuePerWeight(), o1.getValuePerWeight());
    }
});

int currentWeight = 0;
double totalValue = 0;

for (Item item : items) {
    if (currentWeight + item.getWeight() <= bagLimit) {
        // 能装下整个物品，直接放入
        currentWeight += item.getWeight();
        totalValue += item.getValue();
        System.out.printf("放入完整物品：重量%d，价值%d%n", item.getWeight(), item.getValue());
    } else {
        // 装不下整个，取一部分放入（仅适用于分数背包场景）
        int remainingWeight = bagLimit - currentWeight;
        double fraction = (double) remainingWeight / item.getWeight();
        totalValue += fraction * item.getValue();
        currentWeight = bagLimit;
        System.out.printf("放入物品的一部分：重量%d的%.2f，价值%.2f%n",
                item.getWeight(), fraction, fraction * item.getValue());
        break; // 背包已满，停止循环
    }
}

System.out.printf("最终能获得的最大总价值：%.2f%n", totalValue);

为什么不用Map？ #

如果用Map<Integer, Integer>把重量当键、价值当值，会有个致命问题：如果有两个重量相同但价值不同的珠宝，后面的会直接覆盖前面的数据，导致信息丢失。而List<Item>能完整保留所有珠宝的信息，完全适配贪心算法的需求。

内容的提问来源于stack exchange，提问作者user9340719