学习贪心算法01-创新互联

学习贪心算法：

可理解为一种解决问题的思路。当提出一个复杂问题时可以利用创建一个或多个简单的子问题来解决该问题，以得到较优解。用该过程来得到“贪心”的目的。

例题为背包问题——学习自Ramelon的数据结构与算法之贪心算法(JAVA)视频

由该问题引导出的子问题为相比较七个物品的价值量（价值/重量）后择优选取以解决该问题

package lanqiaobei;

public class Demo01 { 

 public static void main(String[] args) {
     int[] weight = {35,30,60,50,40,10,25};
     int[] value = {10,40,30,50,35,40,30};
     int maxWeight = 150;
     AA a = new AA();
     a.good(weight, value, maxWeight);
     
 }
}
class AA {
 public void good(int[]weight,int[]value,int maxWeight) {
     //定义价值量
     double worth[] = new double[weight.length];
     for (int i = 0; i< weight.length; i++) {
         worth[i] = (double)value[i]/weight[i]; 
     }
     //对价值量进行从大到小排序
     for (int i = 0; i<= worth.length-1; i++) {
         for (int j = i; j<= worth.length-2; j++) {
             if (worth[j]<= worth[j+1]) {
                 double temp = worth[j];
                 worth[j] = worth[j+1];
                 worth[j+1] = temp;
             }
         }
     }
     int sum = 0;
     if (maxWeight >= (sum += maxWeight) ) {    
         int i = 0;
         System.out.println("选取价值量为"+worth[i++]+"的物品");
         sum += maxWeight;
     }
 }
}

但是并不是所有问题都可以用贪心算法解决

以上题为例 若要在此基础上，增加要装满背包的要求，则不能用先前的方法解答。回答该问题的方向因从在背包装满的前提下进行装包，而后比较各种装包方式的价值大小选择装包方法。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧