首页 > 代码库 > 贪心算法一：最优装载问题
贪心算法一：最优装载问题
1.基本思想：
贪心算法是通过一系列的选择来得到问题的解，它所做的选择都是当前情况下最优的选择，即贪心算法并不考虑整体最优，而考虑的是当前情况下的局部最优，即贪心选择。
2.贪心算法的两个性质：
1）贪心选择性质：所求解的问题的整体最优解可以通过一系列局部最优的选择来，即贪心选择达到。贪心选择所依赖的是以前所做过的选择，而对以后所做的选择没有关系。
2）最优子结构性质：一个问题的最优解包含其子问题的最优解。
3.贪心算法与动态规划的区别：
动态规划是通过自底向上的方式解决子问题，贪心算法是通过自顶向下的迭代方式做出贪心选择，求解问题的最优解。两共同点是都具有最优子结构性质。
4.最优装载问题：采用重量最轻者先装载的贪心选择策略。
1 #include "stdafx.h" 2 #include <iostream> 3 using namespace std; 4 const int N = 4; 5 template <class type> 6 void Swap(type &x, type &y){ 7 type temp = x; 8 x = y; 9 y = temp;10 }11 void BubleSort(int w[],int t[], int n){12 for (int i = 1; i <= n; i++)13 {14 t[i] = i;15 }16 17 for (int i = 1; i < n; i++)18 {19 int temp = i;20 for (int j =i+1; j <= n; j++){21 if (w[temp]>w[j])22 {23 temp = j;24 Swap(w[i], w[j]);25 } 26 }27 Swap(t[i], t[temp]);28 }29 }30 void BestLoad(int w[], int x[],int c, int n){31 32 int t[N + 1] = {0};//记录原始索引33 BubleSort(w, t, N);34 for (int i = 1; i <= n; i++)35 {36 x[i] = 0;37 }38 for (int i = 1; i <= n&& w[t[i]] <= c; i++)39 {40 x[t[i]] = 1;41 c -= w[t[i]];42 }43 }44 int main(){45 int c = 50;46 int w[] = { 0, 20,10,25,15 };47 int x[N + 1];48 cout << "载重容量为：\n" << c << endl;49 cout << "物品的重量分别为：" << endl;50 for (int i = 1; i <= N; i++)51 {52 cout << w[i] << " ";53 }54 cout << endl;55 BestLoad(w,x, c, N);56 cout << "贪心选择结果为:" << endl;57 for (int i = 1; i <= N; i++)58 {59 cout << x[i] << " ";60 }61 cout << endl;62 }
贪心算法一：最优装载问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。