贪心算法

总是做出在当前看来是最好的选择。

不从整体最优上加以考虑,做出局部最优解。

贪心算法不一定能得到整体最优解，但可以得到整体最优解的近似解。

应用

1、0/1背包问题

一个旅行者有一个最多能装m公斤的背包，现在有n个物品，重量分别是W1,W2,... , Wn 。

每件的价值分别为V1,V2, ... , Vn 。求旅行者能装入的最大总价值及其解向量。

Code

import java.util.*;public class GreedyPackage {public static void main(String[] args) {// 输入流Scanner sc = new Scanner(System.in);System.out.println("请输入物品数量：" );int n = sc.nextInt();System.out.println("请输入物品的重量（以空格间隔）：");int[] w = new int[n];for(int i=0;i v/wdouble[] r = new double[n]; for(int k=0;k记录 w[i] - iMap map = new HashMap();for(int i=0;i选择排序int tempInt;double tempDouble;for(int i=0;i加入背包int total = 0; // 总价值int[] x = new int[n]; // 解向量for(int i=0;i