贪心-01

贪心算法

贪心算法：只顾眼前的苟且。
即在对问题求解时，总是做出在当前看来是最好的选择
其实不懂什么是贪心，为什么那样就是最优解
最优装载问题——加勒比海盗

货物重量：Wi={4,10,7,11,3,5,14,2}
海盗船载重：C
求如何拿货件数最多

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Scanner;

public class 旅人 {
    static int[] w={4, 10, 7, 11, 3, 5, 14, 2};
    static int c=30;
    public static void main(String[] args) {
        int ans=0;
        int temp=0;
        Arrays.sort(w);
        for (int n:w){
            System.out.print(n);
        }
        System.out.println();
        for (int i = 0; i <w.length ; i++) {
            temp+=w[i];
            if (temp>=c){
                if (temp==c){
                    ans=i+1;
                }else {
                    ans=i;
                }
                break;
            }
        }
        System.out.println("能装入的古董最大数量为ans="+ans);
    }
}

听说贪心体现在背包问题上更典型