【趣学算法】Day2 贪心算法——最优装载问题

14天阅读挑战赛
努力是为了不平庸~
算法学习有些时候是枯燥的，这一次，让我们先人一步，趣学算法！

❤️一名热爱Java的大一学生，希望与各位大佬共同学习进步❤️

🧑个人主页：@周小末天天开心

各位大佬的点赞👍 收藏⭐ 关注✅，是本人学习的最大动力

感谢！

📕该篇文章收录专栏—趣学算法

---

目录

一、贪心算法

（1）介绍

（2）注意事项

（3）性质

1）贪心选择

2）最优子结构

二、最优装载问题

（1）古董重量排序

（2）贪心策略选择

模板代码

（1）分析

（2）伪代码

代码优化

（1）分析

（2）伪代码

三、 程序实现

---

一、贪心算法

（1）介绍

贪心算法总是做出当前最好的选择，期望通过局部最优解选择，从而得到全局最优的解决方案。

（2）注意事项

1）一旦做出选择，就不可以回溯。

2）有可能得不到最优解，而是得到最优解的近似值。

3）选择什么样的贪心策略直接决定了算法的好坏。

（3）性质

        人们通过实践发现，利用贪心算法求解的问题往往具有两个重要的性质：贪心选择和最优子结构。只要满足这两个性质，就可以使用贪心算法。

1）贪心选择

        贪心选择是指原问题的整体最优解可以通过一系列局部最优的选择得到：先做出当前最优的选择，将原问题变为一个相似却规模更小的子问题，而后的每一步都是当前最优的选择。这种选择依赖于已做出的选择，但不依赖于未做出的选择。

2）最优子结构

        最优子结构是指原问题的最优解包含子问题的最优解。贪心算法通过一系列的局部最优解（子问题的最优解）得到全局最优解（原问题的最优解），如果原问题的最优解和子问题的最优解没有关系，则求解子问题没有任何意义，无法采用贪心算法。

---

二、最优装载问题

        海盗们截获一艘装满各种各样古董的货船，每一件古董都价值连城，但一旦打碎就会失去其原有的价值。海盗船虽然足够大，但载重量是有限的。海盗船的载重量为W，每件古董的重量为wi，如何才能把尽可能多的古董装上海盗船呢。

（1）古董重量排序

海盗船的载重量w为30。

排序前的古董重量为：

w[i] = {4, 10, 7, 11, 3, 5, 14, 2};

排序后的古董重量为：

w[i] = {2, 3, 4, 5, 7, 10, 11, 14};

（2）贪心策略选择

按照贪心策略，每次选择重量最小的古董装入海盗船（tmp代表已装入的古董重量，ans代表已装入的古董重量）。

1）选择排序后的第1个古董，装入重量tmp = 2，没有超出载重量，ans = 1；

2）选择排序后的第2个古董，装入重量tmp = 2 + 3 = 5，没有超出载重量，ans = 2；

3）选择排序后的第3个古董，装入重量tmp = 5 + 4 = 9，没有超出载重量，ans = 3；

4）选择排序后的第4个古董，装入重量tmp = 9 + 5 = 14，没有超出载重量，ans = 4；

5）选择排序后的第5个古董，装入重量tmp = 14 + 7 = 21，没有超出载重量，ans = 5；

6）选择排序后的第6个古董，装入重量tmp = 21 + 10 =31，没有超出载重量，ans = 6；

当第六次装入古董时可以发现已经超出了船的载重量，所以古董最多装ans = 5个

---

模板代码

（1）分析

        首先使用变量ans记录装入海盗船的古董数量，并使用变量tmp暂存装入海盗船的古董重量。然后依次检查每个古董，对tmp加上改古董的重量，如果小于或的等于载重w，责令ans++，否则退出。

（2）伪代码

int solve1(int n,double W){
	double tmp=0.0;//tmp为已装载到船上的古董重量
    int ans=0; //ans为已装载的古董个数，初始化为0
    for(int i=0;i
        tmp+=w[i];
        if(tmp<=W)
            ans++;
        else
            break;
    }
    return ans;
} 

---

代码优化

（1）分析

实际上，不需要在每次判断是否超出载重时执行ans++，而是可以初始化ans = n。如果已装入海盗船的古董重量tmp大于或等于载重量w，则判断是否刚好等于载重量w并令ans = i + 1，否则令ans = i并退出。这样就只有最后一次才满足条件，ans只需要赋值一次即可，或者所有古董都被装入（初始值n）。

（2）伪代码

int solve2(int n,double w){//优化算法 
	double tmp=0.0;//tmp为已装载到船上的古董重量
	int ans=n; //ans为已装载的古董个数，初始化为n
    for(int i=0;i
        tmp+=w[i];
        if(tmp>=w){//最后一次才满足条件 
        	if(tmp==w)
        		ans=i+1;
        	else
        		ans=i;
        	break;
		}     
    }
    return ans;
}

三、 程序实现

注：程序由Java语言实现

public class algorithm02 {
    public static void main(String[] args) {
        int[] w = {4, 10, 7, 11, 3, 5, 14, 2};
        int W = 30; // 船的载重量
        int temp;
        for (int i = 0; i < w.length-1; i++) {
            for (int j = 0; j < w.length - i - 1; j++) {
                if (w[j] > w[j + 1]) {
                    temp = w[j];
                    w[j] = w[j + 1];
                    w[j + 1] = temp;
                }
            }
        }
        System.out.println("古董重量排序后为：");
        for (int j = 0; j < w.length; j++) {
            System.out.print(w[j] + " ");
        }
            add02 a2 = new add02();
            int ans = a2.solve2(8 , W , w);
            System.out.println("\n总共装入了" + ans + "个古董");
    }
}
 
// add02类
public class add02 {
    public int solve2(int n , int W ,int w[]){//优化算法
        double tmp = 0.0;//tmp为已装载到船上的古董重量
        int ans = 0; //ans为已装载的古董个数，初始化为n
        for(int i = 0; i < n; i++){
            tmp += w[i];
            if(tmp >= W){//最后一次才满足条件
                if(tmp == W)
                    ans = i+1;
                else
                    ans = i;
                break;
            }
        }
        return ans;
    }
}

 得到结果为：

因为船的载重量为30，所以在装入第五个古董后就无法装入第六个了。

我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：

https://cloud.tencent.com/developer/support-plan?invite_code=17cs2zyo455rv