最简单的贪心算法--删除数字问题
给出一个N个数字的数字序列，删除n（n<N）个数字后按原左右次序组成新的正整数，使剩下的数字组成的正整数最大。
分析：将数字序列保存在数组中，每删除一个数字都使剩下的数字组成的正整数最大，并且以它作为下一个删除对象。删除n个数字的全局最优解包含删除一个数字的子问题的最优解。每次删除一个数字，从左往右每相邻的两个数字比较，若左边小于右边则删除左边的那个数字，否则比较下一对数字。每次删完一个数字，后面的元素前进一个位置，并且从头开始比较。
代码：
#include "stdafx.h"#include <iostream>using namespace std;int _tmain(int argc, _TCHAR* argv[]){int i,count;int numberA[200];char numberB[200];cin>>numberB;for (count=0,i=0;numberB[i]!='\0';i++){count++;//记录实际输入数字的个数numberA[i]=numberB[i]-48;//将字符转换成数字放进数组A中}int DelNumCount;//要删除数字个数cout<<"输入要删除的个数：";cin>>DelNumCount;cout<<"以上"<<count<<"位整数中删除"<<DelNumCount<<"个数字分别为："<<endl;i=0;int flag=0,j;int delcount=0;//记录删除个数的临时变量while( DelNumCount>delcount && flag==0 )//没有删够数量，还没有到最后一个数字{i++;if (numberA[i-1] < numberA[i])//前一个数字比后一个数字小，删{cout<<numberA[i-1]<<" ";for (j=i-1;j<=count-delcount-2;j++)//后面的数字依次往前进一格{numberA[j]=numberA[j+1];}delcount++;//删除数量增1i=0;//从头开始查递增区间}if (i==count-delcount-1)//如果是最后一个数字{flag=1;}}cout<<"\n删除后所得最大数为：";for (i=0;i<count-DelNumCount;i++)//依次输出数组中各个数字{cout<<numberA[i];}cout<<endl;return 0;}