删数问题.ppt

删数问题
问题的提出
给定一个n位正整数a,去掉其中任意k≤n个数字后,剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a和正整数k,设计一个算法找出剩下的数字组成的新整数最小的删数方案。
例:a=178543,k=4 输出:13 a=5934625578,k=6 输出:3255
贪心选择策略—建模
n位数a可表示为:
x1x2x3···xixjxkxm ··· xn
要删去k位数,使得剩下的数字组成的整数最小。
设本问题位T,其最优解A=(y1,y2, ···,yk)表示依次删去k个数,在删去k个数后剩下的数字按原次序排成的新数。
即,最优值极为TA。
贪心选择策略—求解
对于a的前r位数:
x1‹x2‹···‹xp‹xq;若xq›xr
则删去xq,即得到一个n-1位的数a1,a1为a去掉一位后,数字按原次序排列最小的一个新正整数,可表示为:
x1x2x3···xpxrxs ··· xn
例:a=45372,其中4‹5›3,则删去5,得a1=4372
a=45732,其中4‹5‹7›3,则删去7,得a1=4532
贪心选择策略—求解
对于a1,原问题T变成了对n-1位数删去k-1位数的新问题T',新问题与原问题相同,只是规模减一。基于此种删数策略,对新问题T',仍可按照上述采用最近下降点删除的贪心选择策略,如此进行下去,直至删去k个数为止。
最优子结构性质—证明
证明最近下降点删除具有最优子结构性质,即对于问题T删除最近下降点xq后,得到的a1是n-1位数中最小的数。
对a按权展开得:
a=x1•10n-1+x2•10n-2+ ···+xp•10n-p+xq•10n-q+xr•10n-r ···+xn
则有:
a1=x1•10n-2+x2•10n-3+ ···+xp•10n-p-1+xr•10n-r+ ···+xn
假