Arithmetic_Thinking -- greedy algorithm

贪心算法--就是一种寻找局部最优解的情况，然后整合成整体最优解的情况

简单的例子：买菜的找钱，现在有1元，5角，1角的硬币，要找给别人2元7角，现在是怎么才能以最少的硬币量找给别人，肯定是先来两个1元的，再来1个5角的，最后两个1角的，但是，这个是我们一眼就能想到的，如何将它抽象成算法的思想呢？

第一步：先找到面值不超过2元7角的最大的硬币，只有1元，还剩下1元7角

第二步：再找到面值不超过1元7角的最大的硬币，只有1元，还剩下7角，

第三步，找到面值不超过7角的最大的硬币，有5角，还剩2角

第四步，找到面值不超过2角的最大的硬币，有1角，还剩1角

第五步，找到面值不超过1角的最大的硬币，有1角，还剩0角

第六步，找到面值不超过0角的最大的硬币，没有，结束

以上其实就是算法的思想，看似很简答，其实也是比较繁琐，最主要的就是找到当前下的最优的解，不管整体怎么样，思想也很简单，但是，什么时候去使用贪心算法，这点就很难了，要满足两个条件，能够找到当前的最优的解，其次最优子结构体是整体最优解的一部分，要使用贪心算法之前你得先要验证是不是可以来使用这个。。。这一点就比较鸡肋了，可是，不管怎么来说，最后能不能得到最优解，贪心算法都是执行效率很高的算法思想。

说了这么多，实践才是验证真理的唯一标准,那我们就来愉快的做个题吧。。。

package thinking;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

import org.junit.Test;

/* QUESTION : optimal loading problem
 * DESCRIBTION : Now we have some boxs need to be loaded into a ship which the limit of its load capacity is C ,and
 *                 every weight of box is designated by the user. The Volume(体积) of this ship isn't limit. So how can 
 *                 we load boxes as many as possible? 
 * 
 * */
class Ship{
    private int capacity;
    public void setCapacity(int capacity) {
        this.capacity = capacity;
    }
    public int getCapacity() {
        return capacity;
    }
}

class Box{
    private int weight;
    public void setWeight(int weight) {
        this.weight = weight;
    }
    public int getWeight() {
        return weight;
    }
}

public class Greedy {
    Ship ship = new Ship();
    Box box1 = new Box();
    Box box2 = new Box();
    Box box3 = new Box();
    Box box4 = new Box();
    Box box5 = new Box();
    @Test
    public void lookingForTheBestChoise(){
        
        // step 1 : initialize the info of ship and boxes
        System.out.println("please input the capacity of ur ship!");
        Scanner scanner = new Scanner(System.in);
        int capacity = scanner.nextInt();
        ship.setCapacity(capacity);
        System.out.println("please input the werght of ur boxes(5)!");
        int b1 = scanner.nextInt();
        int b2 = scanner.nextInt();
        int b3 = scanner.nextInt();
        int b4 = scanner.nextInt();
        int b5 = scanner.nextInt();
        box1.setWeight(b1);
        box2.setWeight(b2);
        box3.setWeight(b3);
        box4.setWeight(b4);
        box5.setWeight(b5);
        List<Box> boxes = new ArrayList<Box>();
        boxes.add(box1);
        boxes.add(box2);
        boxes.add(box3);
        boxes.add(box4);
        boxes.add(box5);
                
        List<Box> sortedList = sort(boxes);
        
        // step 2 : looking for the best solution step by step
        int index = 0;
        while(capacity != 0){
            if(sortedList.get(0).getWeight() > capacity){
                System.out.println("ur capacity of ship is too light!");
                System.exit(0);
            }else{
                if(sortedList.get(index).getWeight() < capacity){
                    System.out.print(sortedList.get(index).getWeight());
                    capacity = capacity-sortedList.get(index).getWeight();
                    index++;
                }else{
                    System.out.println("no more can be loaded");
                    System.exit(0);
                }
            }
        }
        
    }
    
    List<Box> sort(List<Box> boxes){
        //List<Box> sortedList = new ArrayList<Box>();
        for(int i = 0; i<boxes.size(); ++i){
            for(int j = 0; j < boxes.size()-i-1; ++j){
                int tempWeight;
                if(boxes.get(j).getWeight() > boxes.get(j+1).getWeight()){
                    tempWeight = boxes.get(j).getWeight();
                    boxes.get(j).setWeight(boxes.get(j+1).getWeight()); 
                    boxes.get(j+1).setWeight(tempWeight);
                }
            }
        }
        for (Box box : boxes) {
            System.out.println(box.getWeight());
        }
        return boxes;
    }
    public static void main(String[] args) {
        //Scanner s = new Scanner(System.in);
        
    }
}

上面的问题很简单，透过现象看本质就是从小到大一个排序的过程，然后累加。。。还不能很好的体现出贪心的这种感觉，那我们就来一个经典一点的背包问题

package thinking;

import java.util.Scanner;

import org.junit.Test;

/* QUESTION : A traveler has a backpack of up to Mkg, and now has n items, each weighing W1, W2,...Wn.The value of
 *               each piece are respectively C1, C2,...,Cn.the number of each item if enough. The maxinum value of a 
 *               traveler.
 * */

public class PackageQuestion {
    
    int capacity;
    int n; // 物件的数量
    
    @Test
    public void getMaxValue(){
        
        // 输入物件信息
        System.out.println("please input the capacity of backpack!");
        Scanner sca = new Scanner(System.in);
        capacity = sca.nextInt();
        System.out.println("please input the number of the items!");
        n = sca.nextInt();
        int[] weight = new int[n]; // 重量数组
        int[] value = new int[n];  // 对应的价值数组
        int[] index = new int[n];  // 一个额外的记录变化的数组，后面会进行排序交换，所以每一个物品都要贴一个标签
        System.out.println("please input the weight of these items!");
        for(int i = 0; i<n; ++i){
            weight[i] = sca.nextInt();
        }
        System.out.println("please input the value of these items!");
        for(int i =0; i<n; ++i){
            value[i] = sca.nextInt();
        }
        
        //下面就是重场戏了
        // 因为每个物品的重量和价值都不一样，直观可比性不强，所以我们想要一个可以直观比较的参数，进而想到单位重量下的价值
        double[] ev = new double[n]; // 单位重量下的价值数组
        for(int i = 0; i<n; ++i){
            double v = (double)value[i] / (double)weight[i];
            ev[i] = v;
            index[i] = i; //初始化标志
        }
        // 然后下面就是一个复杂的按照价值的由高到低的排序的过程,采用选择排序或者冒泡都可以。
        for(int i = 0; i<n-1; ++i){
            for(int j = i+1; j<n; ++j){
                if(ev[i] < ev[j]){// 前面的单位重量下的价值小于后面的，就交换位置
                    double temp;
                    temp = ev[i];
                    ev[i] = ev[j];
                    ev[j] = temp;
                    // 位置的改变后，一定要注意标志位置的也要改变
                    int temp3 = index[i];
                    index[i] = index[j];
                    index[j] = temp3;
                }
            }
        }
        
        // 用两个新数组来装这个排好序的重量和价值
        int[] wei = new int[n];
        int[] val = new int[n];
        for(int i = 0; i<n; ++i){
            wei[i] = weight[index[i]];
            val[i] = value[index[i]];
        }
        
        //排好序后的监测一下
        System.out.println("weight:");
        for(int i = 0; i<n; ++i){
            System.out.print(wei[i]+"	");
            
        }
        System.out.println("value:");
        for(int i = 0; i<n; ++i){
            
            System.out.print(val[i]+"	");
            
        }
        System.out.println("index:");
        for(int i = 0; i<n; ++i){
        
            System.out.print(index[i]+"	");
        }
        
         //排好序后就开始进行贪心子结构最优化
        int x = 0;
        while(capacity > 0){
            if(wei[0] > capacity){
                System.out.println("ur backpack is too small, get changed!");
                System.exit(0);
            }else{
                if(wei[x] < capacity){
                    System.out.println("get the value is "+val[x]+" item");
                    capacity = capacity-wei[x];
                    x++;
                }else{
                    System.out.println("ur backpack can't pack any more!");
                    System.exit(0);
                }
                
            }
        }
        
    }
    public static void main(String[] args) {

    }
}

上面这个稍微复杂一些，但还是逃脱不开从最值找的一个步骤，只不过这里的最值稍微做了一点技巧就是求了一个单位最值，从而来提高精准度，并且加上了标志数据的标志，思路也是比较简单的。