目录
贪心算法简介
贪心算法总是作出当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的是在某种量度标准上的局部最优解。在使用贪心算法设计求解的过程中，选择能产生问题最优解的最优量度标准是一个核心问题。
对于一个给定的问题,往往可能有好几种量度标准，这些量度标准初看似乎都是可取的。选出最优量度标准并不是一件容易的事，不过，一旦选出某个问题的最优量度标准，那么用贪心算法求解这个问题就特别有效。贪心算法的基本思路是从问题的某个初始解出发，逐步逼近给定的目标，以尽可能快地求得更好的解。当到达算法中的某一步不能再继续前进的时候，算法停止。
实现该算法的过程如下:
货船装箱问题
问题描述:
有一艘货船准备用来装载货物。所有待装货物都装在货箱中且所有货箱的大小都一样，但货箱的重量各不相同。设第i个货箱的重量为w[i]，而货船的最大载重量为c，我们的目的是在体积不受限制的货船上装入最多的货物。
该问题可以形式化描述为:
其中,变量x[i]=0表示第i个货箱不装入货船，x[i]=1表示装入货船。
(1)式是目标函数，(2)式是约束条件。
满足约束条件的任一集合(x[1]…, x[n])是一个可行解(即能装下),使目标函数取最大值的可行解是最优解。
设计思想:
船可以分步装载，每步装一个货箱，且需要考虑装载哪一个货箱。根据这种思想可利用如下贪婪原则:从剩下的货箱中,选择重量最小的货箱。这种选择次序可以保证所选的货箱总重量最小，从而可以装载更多的货箱。根据这种策略，首先选择最轻的货箱，然后选择次轻的货箱，如此下去直到所有的货箱均装上货船，或者货船上不能再容纳其它任何一个货箱，即不能超出最大载重量。
假设有8个货箱 n=8，每个货箱的重量分别是w[1,2,…,n]=[150,200,50,30,70,90,100,80],货船的总装载重量是c=400。利用贪心算法时,所要考察货箱的顺序为4,3,5,8,6,7,1,2。而货箱4,3,5,8,6的总重量为320（30+50+70+80+90）个单位且已被装载,剩下的装载能力为80个单位,小于剩下的任何一个货箱。在这种贪心算法解决当中得到[x[1],x[2],…,x[n]]=[0,0,1,1,1,1,0,1],∑x[i]=5(1≤i≤8)，简而言之，选择了3，4，5，6，8号货箱，共5个。
具体算法描述:
#include <iostream>
#include <algorithm>
#include <utility>
using namespace std;
const int N = 100; // 假设货箱数量不超过100
int n, c;
int w[N];
int x[N] = { 0 }; //0表示不选择，1表示选择
int main() {
cin >> n >> c;
pair<int, int> a[N]; // 用于记录原始索引和重量的pair
for (int i = 0; i < n; i++) {
cin >> w[i];
a[i] = make_pair(w[i], i + 1);
}
// 按照货箱重量从小到大排序
sort(a, a + n);
int sum = 0;// 已经装载的货箱总重量
int count = 0;//已装载的货箱数量
for (int i = 0; i < n; i++) {
int weight = a[i].first;
int index = a[i].second;
// 如果加上当前货箱的重量没有超过货船的最大载重量
if (sum + weight <= c) {
x[index - 1] = 1; // 选择这个货箱
sum += weight; // 更新已装载的货箱总重量
count++;
}
}
cout << "共装载" << count << "个货箱：";
for (int i = 0; i < n; i++)
if (x[i] == 1) cout << i + 1<<' ';
cout << "\n重量分别是：";
for (int i = 0; i < n; i++)
if (x[i] == 1) cout << w[i] << ' ';
return 0;
}算法证明
贪心法求解问题具有的性质:
贪心选择性质：贪心选择，在每一步选择中，我们都会做出在当前看来是最好的选择，这个选择依赖于之前所做的选择，但不依赖于未来的选择。在货船装箱问题的贪心算法中，我们按照货箱重量的升序进行选择，每一步都选择当前可以装载的最小重量的货箱。
最优子结构性质：最优子结构性质是指一个问题的最优解包含其子问题的最优解。对于货船装箱问题，如果一个问题的最优解存在，则它的最优子集也存在最优解，并且问题的最优解可以通过组合子问题的最优解来构造。
数学归纳法证明贪心选择性质:
特殊情况:当没有剩余的货箱需要装载时（即count=n时，所有的货箱都已经被装载)
其余情况：
归纳假设:假设对于所有重量不超过 C 的货箱集合，贪心算法能够找到最优解。
归纳步骤:考虑一个重量为 C + x（其中 x>0）的货箱集合。我们的目标是证明贪心算法也能找到这个集合的最优解。
证明:
1. 根据归纳假设，首先从所有重量不超过 C 的货箱中选择一个最优子集。这个子集的总重量不超过 C ，并且是最优的，因 为它是上一阶段根据贪心算法选择的。 2. 现在考虑是否加入一个新的货箱，其重量为 x如果这个新货箱被装载，那么它将替换掉原来子集中的一个或多个货箱，因为需要保持总重量不超过 W + x。由于贪心算法总是选择最小的重量，这个新货箱的加入将使得总重量增加，但不会增加到超过 W + x 。
如果这个新货箱不被装载，那么保持原来的最优子集不变，因为它已经是在不超过 C 的条件下的最优解。
最后，在这两种情况下，都得到了一个在不超过 W + x 条件下的最优解。这就证明了，即使加入了新的重量为 x的货箱，贪心算法仍然能够找到最优解。
反证法证明最优子结构性质:
假设：这个问题的最优解 S 不包含其子问题的最优解。也就是说，存在一个子集 S′，它是S 的一部分，但 S′ 不是其子集问题的最优解。
由于 S′ 不是其子集问题的最优解，那么必然存在另一个解 S′′，使得 S′ ′是 S′ 的子集问题的最优解，并且 S′′比 S′ 更优或者至少同样优。 如果将 S′ ′替换 S′ 中的相应子集，将得到一个新的解 S′′′。由于 S′′是一个更优或者同样优的解， S′′′也将是一个更优或者同样优的解。 通过这种方式，可以逐步替换 S中的所有子集，直到得到一个完全由最优子集解构成的解S ′ ~ ′ 。
它显然优于或等于 S，如果 S ′ ~ ′优于 S，那么 S不能是最优解，可以推出 S ′ ~ ′是问题的最优解；如果 S ′ ~ ′与S同样优，那么 S就不是唯一的最优解，因为 S ′ ~ ′也是最优解。
这与原假设相矛盾，货船装箱问题的最优解确实包含其子问题的最优解，这就证明了最优子结构性质。
总结
时间复杂度分析：程序主要计算量在于将货箱依照其重量从小到大的顺序排序，使用的是algorithm库中的sort函数对包含重量和索引的 pair 数组进行排序。在最坏情况下，排序的时间复杂度是 O(nlogn)，其中 n 是货箱的数量。
总的来说，贪心算法是一种有效的问题求解策略，尤其适用于那些可以分解为最优子结构的问题。然而，它所做出的仅是在某种量度标准上的局部最优解，并非所有问题都可以用贪心算法来解决，且贪心算法并不总能保证得到全局最优解。
标签：货箱,int,货船,算法,最优,装箱,贪心 From： https://blog.csdn.net/lsfff666/article/details/137202535