背包问题简介
背包问题是一个经典的组合优化问题，基本描述是：给定一组物品，每种物品都有自己的重量和价值，在限定的总重量内，我们如何选择,才能使物品的总价值最大。
（图片来源网络，侵删）
根据物品是否可以分割,背包问题可以分为三类：
- 0/1 背包问题：每种物品要么完整地放入背包，要么不放入,不能分割。
- 完全背包问题：每种物品都有无限件,可以无限次放入背包。
- 分数背包问题：每种物品都可以分割成任意大小,可以只放入物品的一部分。
贪心算法主要适用于分数背包问题，因为它可以处理物品的分割，对于 0/1 背包问题,贪心算法通常无法得到最优解。
贪心算法解决分数背包问题
核心思想
贪心算法在每一步都做出当前看起来最优的选择，期望通过一系列局部最优的选择,最终达到全局最优。
对于分数背包问题，这个“最优”的选择标准是：优先选择“性价比”最高的物品。
（图片来源网络，侵删）
- 性价比 = 物品的价值 / 物品的重量
算法步骤如下：
- 计算性价比：计算所有物品的性价比（
value / weight）。 - 排序：将所有物品按照性价比从高到低进行排序。
- 贪心选择：
- 按照排序后的顺序,依次遍历每个物品。
- 如果当前物品的整个重量都可以放入剩余的背包容量中，则将其全部放入，背包容量减去该物品的重量,总价值加上该物品的价值。
- 如果当前物品的整个重量无法放入剩余的背包容量中，则将其一部分（即剩余的背包容量）放入，背包容量变为 0,总价值加上这部分的价值。
- 如果背包容量已经为 0,则算法结束。
为什么贪心算法对分数背包有效？
因为在分数背包中，物品可以被分割，所以我们可以优先装满性价比最高的“空间”，即使一个物品装不下，也可以只装它的一部分，从而保证没有浪费任何高价值的“单位重量”空间，这使得局部最优的选择（选性价比最高的）能够导向全局最优。
Java 代码实现
下面是一个完整的 Java 实现，包括 Item 类、贪心算法实现和主函数测试。
代码结构
Item.java: 一个简单的 Java Bean，用于表示物品的属性（名称、重量、价值）。FractionalKnapsack.java: 包含贪心算法的核心逻辑。Main.java: 主类，用于创建物品、调用算法并打印结果。
Item.java
// Item.java
public class Item {
private String name;
private double weight;
private double value;
public Item(String name, double weight, double value) {
this.name = name;
this.weight = weight;
this.value = value;
}
// 计算性价比
public double getRatio() {
if (weight == 0) {
return 0; // 避免除以零
}
return value / weight;
}
// Getters
public String getName() { return name; }
public double getWeight() { return weight; }
public double getValue() { return value; }
@Override
public String toString() {
return String.format("Item{name='%s', weight=%.2f, value=%.2f, ratio=%.2f}",
name, weight, value, getRatio());
}
}
FractionalKnapsack.java
// FractionalKnapsack.java
import java.util.Arrays;
import java.util.Comparator;
public class FractionalKnapsack {
/**
* 使用贪心算法解决分数背包问题
* @param items 物品数组
* @param capacity 背包的总容量
* @return 最大可达到的总价值
*/
public double getMaxValue(Item[] items, double capacity) {
// 1. 按照性价比从高到低对物品进行排序
// 使用 Java 8 的 Lambda 表达式进行自定义排序
Arrays.sort(items, new Comparator<Item>() {
@Override
public int compare(Item a, Item b) {
// 降序排序，b.getRatio() - a.getRatio() 会得到从大到小的顺序
return Double.compare(b.getRatio(), a.getRatio());
}
});
// 或者更简洁的 Lambda 写法:
// Arrays.sort(items, (a, b) -> Double.compare(b.getRatio(), a.getRatio()));
double totalValue = 0.0; // 总价值
double remainingCapacity = capacity; // 剩余背包容量
// 2. 遍历排序后的物品列表
for (Item item : items) {
if (remainingCapacity == 0) {
// 背包已满，结束循环
break;
}
// 如果当前物品可以完全放入背包
if (item.getWeight() <= remainingCapacity) {
totalValue += item.getValue();
remainingCapacity -= item.getWeight();
System.out.println("放入整个物品: " + item.getName() +
", 当前价值: " + totalValue +
", 剩余容量: " + remainingCapacity);
} else {
// 如果当前物品不能完全放入，则放入一部分
double fraction = remainingCapacity / item.getWeight();
double addedValue = item.getValue() * fraction;
totalValue += addedValue;
remainingCapacity = 0; // 背包被装满
System.out.println("放入物品 " + item.getName() + " 的 " +
String.format("%.2f", fraction * 100) + "%" +
", 当前价值: " + totalValue +
", 剩余容量: " + remainingCapacity);
}
}
return totalValue;
}
}
Main.java (测试)
// Main.java
public class Main {
public static void main(String[] args) {
// 创建物品列表
Item[] items = {
new Item("物品A", 10, 60), // 性价比 = 6.0
new Item("物品B", 20, 100), // 性价比 = 5.0
new Item("物品C", 30, 120) // 性价比 = 4.0
};
double knapsackCapacity = 50; // 背包容量
System.out.println("初始物品列表:");
for (Item item : items) {
System.out.println(item);
}
System.out.println("--------------------------------------------------");
System.out.println("背包容量: " + knapsackCapacity);
System.out.println("--------------------------------------------------");
// 创建 FractionalKnapsack 实例并求解
FractionalKnapsack fk = new FractionalKnapsack();
double maxValue = fk.getMaxValue(items, knapsackCapacity);
System.out.println("--------------------------------------------------");
System.out.println("在背包容量为 " + knapsackCapacity + " 的情况下，可以获得的最大价值为: " + maxValue);
}
}
运行结果
初始物品列表:
Item{name='物品A', weight=10.00, value=60.00, ratio=6.00}
Item{name='物品B', weight=20.00, value=100.00, ratio=5.00}
Item{name='物品C', weight=30.00, value=120.00, ratio=4.00}
--------------------------------------------------
背包容量: 50.0
--------------------------------------------------
放入整个物品: 物品A, 当前价值: 60.0, 剩余容量: 40.0
放入整个物品: 物品B, 当前价值: 160.0, 剩余容量: 20.0
放入物品 物品C 的 66.67%, 当前价值: 240.0, 剩余容量: 0.0
--------------------------------------------------
在背包容量为 50.0 的情况下，可以获得的最大价值为: 240.0结果分析：
（图片来源网络，侵删）
- 算法首先按性价比排序：物品A (6.0) > 物品B (5.0) > 物品C (4.0)。
- 先放入整个物品A（重量10），价值60,剩余容量40。
- 接着放入整个物品B（重量20），价值100，总价值160,剩余容量20。
- 物品C（重量30）无法完全放入，放入其 20/30 = 2/3 的部分，价值增加 120 * (2/3) = 80，总价值 160 + 80 = 240,背包被装满。
- 最终最大价值为 240,这是该情况下的最优解。
为什么贪心算法不适用于 0/1 背包问题？
为了说明这一点,我们看一个简单的反例。
场景：
- 背包容量：
W = 50 - 物品列表：
- 物品A：重量
w1 = 10，价值v1 = 60(性价比 = 6) - 物品B：重量
w2 = 20，价值v2 = 100(性价比 = 5) - 物品C：重量
w3 = 30，价值v3 = 150(性价比 = 5)
- 物品A：重量
贪心算法的选择过程：
- 按性价比排序：A (6) > B (5) = C (5)，假设 B 和 C 性价比相同，我们按任意顺序，比如先选 B。
- 选择物品A，放入背包，剩余容量
50 - 10 = 40，总价值60。 - 选择物品B，放入背包，剩余容量
40 - 20 = 20，总价值60 + 100 = 160。 - 物品C（重量30）无法放入,结束。
- 贪心算法得到的价值：160。
真正的最优解：
- 不选物品A。
- 选择物品B和物品C，总重量
20 + 30 = 50,正好装满背包。 - 最优价值：
100 + 150 = 250。
贪心算法得到的解（160）远小于最优解（250），因为它在第一步就做出了局部最优的选择（放入性价比最高的A），但这导致它错过了由B和C组合产生的更大的全局最优解，贪心算法无法保证在0/1背包问题中得到最优解，这类问题通常需要使用动态规划来解决。
