2023年8月1日发(作者：)

贪⼼算法_01背包问题_Java实现原⽂地址：

本⽂出⾃：【梁敬明的博客】1.贪⼼算法　　什么是贪⼼算法？是指在对问题进⾏求解时，总是做出当前看来是最好的选择。也就是说，不从整体最优上加以考虑，所得出的结果仅仅是某种意义上的局部最优解。因此贪⼼算法不会对所有问题都能得到整体最优解，但对于很多问题能产⽣整体最优解或整体最优解的近似解。2背包问题　　　　⼀个旅⾏者有⼀个最多能装m公⽄的背包，现在有n中物品，每件的重量分别是W1、W2、……、Wn，每件物品的价值分别为C1、C2、……、Cn， 需要将物品放⼊背包中，要怎么样放才能保证背包中物品的总价值最⼤？3.算法分析　　　　当遇到这样的问题，我们可以换⼀种⾓度去思考，假设在⼀个100m3的房⼦⾥⾯，现在要将房⼦装满，同时要保证放⼊的物品个数最多以及装⼊的东西最重，现在⾝边有铁球和棉花，请问⼤家是放铁球进去好呢还是放棉花进去好呢？显⽽易见，放⼊铁球进去是最优选择。但是原因是什么呢？很简单，就是因为铁球的密度较⼤，相同体积的铁球和棉花相⽐，铁球更重。

　　不过前提是放⼊第⼀个铁球时，铁球的体积V1⼩于等于100m3 ；放⼊第⼆个铁球时，铁球的体积V2 ⼩于等于(100-V1)m3;……；放⼊第n个铁球时，铁球的体积⼩于等于（100- ∑n1Vn-1）m3 ，要是第n个铁球的体积⼤于（100- ∑n1Vn-1）m3 ，还真是不如放点单位体积更轻的棉花进去，说的极端点就是所有铁球的体积都⼤于100m3 ，还真不如随便放⼊点棉花进去合算。所以总是放铁球进去，不考虑是否放⼊棉花，容易产⽣闲置空间，最终会得不到最优选择，可能只是最优选择的近似选择。

　　现在再次回到背包问题上，要使得背包中可以获得最⼤总价值的物品，参照铁球的例⼦我们可以知道选择单位重量下价值最⾼的物品放⼊为最优选择。但是由于物品不可分割，⽆法保证能将背包刚好装满，最后闲置的容量⽆法将单位重量价值更⾼的物品放⼊，此时要是可以将单位重量价值相对低的物品放⼊，反⽽会让背包的总价值和单位重量的价值更⾼。假设现在背包的剩余总重量为5kg，存在⼀个4kg价值为4.5的物品，⼀个3kg价值为3的物品，⼀个2kg价值为2的物品，很显然将3kg和2kg的物品放⼊背包中所获得的价值更⾼,虽然没有4kg的物品单位重量的价值⾼。因此通过贪⼼算法求解01背包的问题可能得不到问题的最优解，得到的是近似最优解的解。

　　创建⼀个物品对象，分别存在价值、重量以及单位重量价值三种属性。public class Knapsack implements Comparable { /** 物品重量 */ private int weight; /** 物品价值 */ private int value; /** 单位重量价值 */ private int unitValue; public Knapsack(int weight, int value) { = weight; = value; lue = (weight == 0) ? 0 : value / weight; } public int getWeight() { return weight; } public void setWeight(int weight) { = weight; } public int getValue() { return value; } public void setValue(int value) { = value; } public int getUnitValue() { return unitValue; } @Override public int compareTo(Knapsack snapsack) { int value = lue; if (unitValue > value) return 1; if (unitValue < value) return -1; return 0; }}按照贪⼼算法将物品放⼊背包中。public class TXSFProblem { // 现有的物品 private Knapsack[] bags; // 背包的总承重 private int totalWeight; // 背包最⼤总价值 private int bestValue; public TXSFProblem(Knapsack[] bags, int totalWeight) { = bags; eight = totalWeight; // 对背包按单位重量价值从⼤到⼩排序 (bags, eOrder()); } public void solve() { int tempWeight = totalWeight; for (int i = 0; i < ; i++) { //判断当前物品是否可以放⼊背包中，若不能则继续循环，查找下⼀个物品 if (tempWeight - bags[i].getWeight() < 0) continue; tempWeight -= bags[i].getWeight(); bestValue += bags[i].getValue(); } } public int getBestValue() { return bestValue; }}测试最终结果：85（实际最优结果为90）public class TXSFTest { public static void main(String[] args) { Knapsack[] bags = new Knapsack[] { new Knapsack(2, 13), new Knapsack(1, 10), new Knapsack(3, 24), new Knapsack(2, 15), new Knapsack(4, 28), new Knapsack(5, 33), new Knapsack(3, 20), new Knapsack(1, 8) }; int totalWeight = 12; TXSFProblem problem = new TXSFProblem(bags, totalWeight); (); n(tValue()); }}欢迎关注我的微信公众号：“”Java⾯试通关⼿册（坚持原创，分享美⽂，分享各种Java学习资源，⾯试题，以及企业级Java实战项⽬回复关键字免费领取）：

2023年8月1日发(作者：)

贪⼼算法_01背包问题_Java实现原⽂地址：

本⽂出⾃：【梁敬明的博客】1.贪⼼算法　　什么是贪⼼算法？是指在对问题进⾏求解时，总是做出当前看来是最好的选择。也就是说，不从整体最优上加以考虑，所得出的结果仅仅是某种意义上的局部最优解。因此贪⼼算法不会对所有问题都能得到整体最优解，但对于很多问题能产⽣整体最优解或整体最优解的近似解。2背包问题　　　　⼀个旅⾏者有⼀个最多能装m公⽄的背包，现在有n中物品，每件的重量分别是W1、W2、……、Wn，每件物品的价值分别为C1、C2、……、Cn， 需要将物品放⼊背包中，要怎么样放才能保证背包中物品的总价值最⼤？3.算法分析　　　　当遇到这样的问题，我们可以换⼀种⾓度去思考，假设在⼀个100m3的房⼦⾥⾯，现在要将房⼦装满，同时要保证放⼊的物品个数最多以及装⼊的东西最重，现在⾝边有铁球和棉花，请问⼤家是放铁球进去好呢还是放棉花进去好呢？显⽽易见，放⼊铁球进去是最优选择。但是原因是什么呢？很简单，就是因为铁球的密度较⼤，相同体积的铁球和棉花相⽐，铁球更重。

　　不过前提是放⼊第⼀个铁球时，铁球的体积V1⼩于等于100m3 ；放⼊第⼆个铁球时，铁球的体积V2 ⼩于等于(100-V1)m3;……；放⼊第n个铁球时，铁球的体积⼩于等于（100- ∑n1Vn-1）m3 ，要是第n个铁球的体积⼤于（100- ∑n1Vn-1）m3 ，还真是不如放点单位体积更轻的棉花进去，说的极端点就是所有铁球的体积都⼤于100m3 ，还真不如随便放⼊点棉花进去合算。所以总是放铁球进去，不考虑是否放⼊棉花，容易产⽣闲置空间，最终会得不到最优选择，可能只是最优选择的近似选择。

　　现在再次回到背包问题上，要使得背包中可以获得最⼤总价值的物品，参照铁球的例⼦我们可以知道选择单位重量下价值最⾼的物品放⼊为最优选择。但是由于物品不可分割，⽆法保证能将背包刚好装满，最后闲置的容量⽆法将单位重量价值更⾼的物品放⼊，此时要是可以将单位重量价值相对低的物品放⼊，反⽽会让背包的总价值和单位重量的价值更⾼。假设现在背包的剩余总重量为5kg，存在⼀个4kg价值为4.5的物品，⼀个3kg价值为3的物品，⼀个2kg价值为2的物品，很显然将3kg和2kg的物品放⼊背包中所获得的价值更⾼,虽然没有4kg的物品单位重量的价值⾼。因此通过贪⼼算法求解01背包的问题可能得不到问题的最优解，得到的是近似最优解的解。

　　创建⼀个物品对象，分别存在价值、重量以及单位重量价值三种属性。public class Knapsack implements Comparable { /** 物品重量 */ private int weight; /** 物品价值 */ private int value; /** 单位重量价值 */ private int unitValue; public Knapsack(int weight, int value) { = weight; = value; lue = (weight == 0) ? 0 : value / weight; } public int getWeight() { return weight; } public void setWeight(int weight) { = weight; } public int getValue() { return value; } public void setValue(int value) { = value; } public int getUnitValue() { return unitValue; } @Override public int compareTo(Knapsack snapsack) { int value = lue; if (unitValue > value) return 1; if (unitValue < value) return -1; return 0; }}按照贪⼼算法将物品放⼊背包中。public class TXSFProblem { // 现有的物品 private Knapsack[] bags; // 背包的总承重 private int totalWeight; // 背包最⼤总价值 private int bestValue; public TXSFProblem(Knapsack[] bags, int totalWeight) { = bags; eight = totalWeight; // 对背包按单位重量价值从⼤到⼩排序 (bags, eOrder()); } public void solve() { int tempWeight = totalWeight; for (int i = 0; i < ; i++) { //判断当前物品是否可以放⼊背包中，若不能则继续循环，查找下⼀个物品 if (tempWeight - bags[i].getWeight() < 0) continue; tempWeight -= bags[i].getWeight(); bestValue += bags[i].getValue(); } } public int getBestValue() { return bestValue; }}测试最终结果：85（实际最优结果为90）public class TXSFTest { public static void main(String[] args) { Knapsack[] bags = new Knapsack[] { new Knapsack(2, 13), new Knapsack(1, 10), new Knapsack(3, 24), new Knapsack(2, 15), new Knapsack(4, 28), new Knapsack(5, 33), new Knapsack(3, 20), new Knapsack(1, 8) }; int totalWeight = 12; TXSFProblem problem = new TXSFProblem(bags, totalWeight); (); n(tValue()); }}欢迎关注我的微信公众号：“”Java⾯试通关⼿册（坚持原创，分享美⽂，分享各种Java学习资源，⾯试题，以及企业级Java实战项⽬回复关键字免费领取）：