【算法分析与设计期末复习】贪心算法交换论证

给定正整数数组A，请设计一个方法把这些整数拼接起来，使得拼接结果数最大。例如：A = [1, 32, 212]，拼接结果为322121。
1）设计一个贪心算法，输出拼接结果（字符串格式），并分析算法的复杂度；（15分）
2）证明该算法的正确性。（10分）
答案：
1） 对于所有整数按照字典序降序排列，然后依次拼接整数，输出字符序列。
复杂度为O(nlgn)
参考程序如下：

#include 
#include 
#include 
#include 
using namespace std;
struct cmp{bool operator()(const string &a,const string &b){string s1=a+b;string s2=b+a;return s1>s2;}
};
bool comp(const string &a,const string &b){string s1=a+b;string s2=b+a;return s1>s2;
}
void getMaxNum(const vector<int> &A,int n){vector<string> str(n);for(int i=0;i<n;i++){stringstream ss;ss<<A[i];ss>>str[i];}sort(str.begin(),str.end(),cmp());//sort(str.begin(),str.end(),comp);for(int i=0;i<n;i++)cout<<str[i];cout<<endl;
}
int main()
{int n;while(cin>>n){vector<int> A(n);for(int i=0;i<n;i++)cin>>A[i];getMaxNum(A,n);}return 0;
}

2） 用交换论证法证明。第一步，给定假设的最优解，按照贪心策略替换排第一的拼接整数，可以证明不改变最优性；第二步，对于子问题（剔除排第一的拼接整数），满足最优子结构性质，即对于子问题可以继续替换。（证明思想）

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！