🎯目的：
1）了解贪心算法思想及基本原理；
2）掌握使用贪心算法求解问题的一般特征；
3）能够针对实际问题，能够正确选择贪心策略；
4）能够针对选择的贪心策略，证明算法的正确性；
5）能够根据贪心策略，正确编写代码；
6）能够正确分析算法的时间复杂度和空间复杂度。
🎯内容：
实现最优装载的贪心算法。
测试数据可选用：
假设轮船限重12kg
i
1
2
3
4
5
Wi（kg）
8
4
2
5
7
🎯代码（Java）：
package one; import java.util.Vector; public class Two { public static void main(String[] args) { // TODO Auto-generated method stub thing t1 = new thing(1, 8); thing t2 = new thing(2, 4); thing t3 = new thing(3, 2); thing t4 = new thing(4, 5); thing t5 = new thing(5, 7); Vector<thing> v = new Vector<thing>(); v.add(t1); v.add(t2); v.add(t3); v.add(t4); v.add(t5); // 按重量排序 for (int i = 0; i < 5; i++) { for (int j = 0; j < 4 - i; j++) { if (v.get(j).Wi > v.get(j + 1).Wi) { thing t = v.get(j); v.set(j, v.get(j + 1)); v.set(j + 1, t); } } } int w = 0; int Weight = 12; System.out.println("选中的编号为："); for (int i = 0; i < 5; i++) { if (v.get(i).Wi + w <= Weight) { w += v.get(i).Wi; System.out.println(v.get(i).x); } } } } class thing { int x; int Wi; public thing(int x, int wi) { super(); this.x = x; Wi = wi; } @Override public String toString() { return "thing [x=" + x + ", Wi=" + Wi + "]"; } }
🎯 运行结果：
🎯算法分析：
当储存n个对象时，
1.时间复杂度分析：
- 对于排序操作，这里使用的是冒泡排序的方法，外层循环n次，内层循环了（n-1）次、(n-2)次、(n-3)次...1次，因此，排序操作的时间复杂度为O(n+(n-1)+(n-2)+...+1)=O(n^2).
- 循环遍历vector的元素，执行n次，因此，该循环的时间复杂度为：O(n^2)。
综上所述：整段代码在存储n个对象时的时间复杂度为O(n^2)。
2.空间复杂度分析：
- 声明了一个Vector对象v，其存储n个thing对象。因此，存储空间复杂度为：O(n)。
- 声明了若干个int类型的变量w、weight、以及n个thing对象。因为这些变量和对象的数量随着输入规模的增加而增加，所以额外的时间复杂度可以看作O(n)。
综上所述，整段代码在存储n个对象的空间复杂度为O(n)。
需要注意的是，上述分析假设输入规模n是固定的。如果输入规模n增加，例如thing对象的个数增加时，时间复杂度和空间复杂度可能会发生变化。但在给定的固定输入规模下，该代码的时间复杂度为O(n^2)，空间复杂度为O(n)。因此，在处理大规模输入时要注意性能问题。
🎯其他程序语言的实现：
注：以下代码均有ai生成，读者如发现bug可以发在评论区，咱们一起解决❤️！
🎐c语言程序：
#include <stdio.h> typedef struct { int x; int Wi; } Thing; void bubbleSort(Thing arr[], int n) { for (int i = 0; i < n; i++) { for (int j = 0; j < n - i - 1; j++) { if (arr[j].Wi > arr[j + 1].Wi) { Thing temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } int main() { Thing t1 = {1, 8}; Thing t2 = {2, 4}; Thing t3 = {3, 2}; Thing t4 = {4, 5}; Thing t5 = {5, 7}; Thing v[5] = {t1, t2, t3, t4, t5}; int size = 5; int w = 0; int Weight = 12; bubbleSort(v, size); printf("选中的编号为：\n"); for (int i = 0; i < size; i++) { if (v[i].Wi + w <= Weight) { w += v[i].Wi; printf("%d\n", v[i].x); } } return 0; }
注意事项：
- 在C语言中，没有直接对应Java的
Vector类，而是使用了数组。 - 在C语言中，没有自带的冒泡排序函数，需要实现自己的排序逻辑。
🎐 python代码：
class Thing: def __init__(self, x, Wi): self.x = x self.Wi = Wi t1 = Thing(1, 8) t2 = Thing(2, 4) t3 = Thing(3, 2) t4 = Thing(4, 5) t5 = Thing(5, 7) v = [t1, t2, t3, t4, t5] # 按重量排序 for i in range(5): for j in range(4 - i): if v[j].Wi > v[j + 1].Wi: v[j], v[j + 1] = v[j + 1], v[j] w = 0 Weight = 12 print("选中的编号为：") for i in range(5): if v[i].Wi + w <= Weight: w += v[i].Wi print(v[i].x)
注意事项：
- Python中没有严格定义类的访问修饰符，所以不需要使用public关键字。
- Python中的列表使用方括号[]表示，而不是Java中的Vector。
- 在Python中，排序可以使用列表的sort()方法或者sorted()函数进行。在这里简单起见，使用了冒泡排序算法。
🎐C++代码：
#include <iostream> #include <vector> using namespace std; class Thing { public: int x; int Wi; Thing(int x, int wi) { this->x = x; Wi = wi; } string toString() { return "thing [x=" + to_string(x) + ", Wi=" + to_string(Wi) + "]"; } }; int main() { Thing t1(1, 8); Thing t2(2, 4); Thing t3(3, 2); Thing t4(4, 5); Thing t5(5, 7); vector<Thing> v; v.push_back(t1); v.push_back(t2); v.push_back(t3); v.push_back(t4); v.push_back(t5); // 按重量排序 for (int i = 0; i < 5; i++) { for (int j = 0; j < 4 - i; j++) { if (v[j].Wi > v[j + 1].Wi) { Thing t = v[j]; v[j] = v[j + 1]; v[j + 1] = t; } } } int w = 0; int Weight = 12; cout << "选中的编号为：" << endl; for (int i = 0; i < 5; i++) { if (v[i].Wi + w <= Weight) { w += v[i].Wi; cout << v[i].x << endl; } } return 0; }
注意事项：
- C++中使用
#include <vector>引入向量（Vector）的类。 - 在C++中，使用
push_back()方法向向量中添加元素。 - 在C++中，使用
cout和endl来进行输出。
