学校期末考试版-贪心算法（最优转载问题）java

问题：

有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为wi。最优装载问题要求在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。

举例：假设c=20，w={5,6,7,8,9}，则输出 5 6 7

算法设计

贪心算法：
（1）贪心策略：
首先要确定贪心策略，选择当前看上去最好的一个方案。例如，挑选苹果，如果你认为大的是最好的，那你每次都从苹果堆中拿一个最大的，作为局部最优解，贪心策略就是选择当前最大的苹果；假如你认为最红的苹果是最好
的，那你每次都从苹果堆中拿一个最红的，贪心策略就是选择当前最好的苹果。因此根据求解目标不同，贪心策略也会不同。对于这道题的贪心策略就是每次选择重量最小的集装箱，就能保证装载的集装箱最多。
（2）局部最优解
根据贪心策略，一步一步地得到局部最优解。例如，第一次选择一个最大的苹果为a1，第二次再从剩下的苹果堆中选择一个最大的苹果放起来，记为a2，以此类推。同理可得，第一次选择最轻的集装箱，第二次再从剩下的集装箱中选择最轻的，以此类推.
（3）全局最优解
把所有的局部最优解合成为原来问题的一个最优解（a1,a2,…）
解题思路：
（1）当载重量为定值c时，wi越小时，可装载的集装箱数量n就越大，只有依次选择最小重量的古董，直到不能再装为止。
（2）把n个集装箱的重量从小到大排序，然后根据贪心策略尽可能多地选择前i个集装箱，直到不能继续装为止，此时达到最优。

代码

import java.util.Arrays;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int c;
        System.out.println("请输入轮船的容量c：");
        c=sc.nextInt();
        System.out.println("请输入集装箱的数量n:");
        int tmp=0;//tmp为已经装载到船上的集装箱重量
        int count=0;//已经已经装载的数量
        int n=sc.nextInt();
        int  []w=new int[n];
        int []ans=new int[n];//ans为已经装上的集装箱
        System.out.println("请输入每个集装箱的重量：");
        for (int i=0;i<n;i++){
            w[i]=sc.nextInt();
        }
        Arrays.sort(w);//将数组从小到大排序，使后面的重量越来越大，当前面的某一个不能满足时，后面的也无法满足，方便退出循环。
        for (int  i=0;i<n;i++){
            tmp+=w[i];
            if(tmp<=c){
                ans[i]=w[i];
                count++;
            }
            else
                break;;
        }
        System.out.println("装入的集装箱的重量为：");
        for (int i=0;i<count;i++){
            System.out.print(ans[i]+" ");
        }
    }
}

输入

20
5
5 6 7 8 9

输出

5 6 7   

运行示例