删数题目[精品]

删数问题 岗淮暴不疏涪源流痊赔多反庭疥可熙翻侧瞪郭晾冀汹敲毯器顿翟扩谩位佣删数问题删数问题 问题的提出 给定一个n位正整数a 去掉其中任意k n个数字后 剩下的数字按原次序排列组成一个新的正整数 对于给定的n位正整数a和正整数k 设计一个算法找出剩下的数字组成的新整数最小的删数方案 例 a 178543 k 4输出 13a 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 4372a 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假设删去的不是xq 而是其它位 则有 a2 x1 10n 2 x2 10n 3 xp 10n p 1 xq 10n q xn因为有x1 x2 xp xq且xq xr 则有a1 a2 因此 删数问题满足最优子结构性质 寂术咆揭荧鞠塔沮更歹丧团日饥三蓉久企文谨瀑复贬贤硫膛然枪珊稽豢增删数问题删数问题 贪心选择性质 证明 设问题T已按照最近下降点的方法删除 A y1 y2 yk 是删数问题的一个最优解 易知 若问题有解 则1 k n 1 当k 1时 由前得证 A y1 A 是问题的最优解 2 当k q时 由反证法 可得A y1 y2 yq 是最优解 当k q 1时 由前得证 A y1 y2 yq yq 1 是最优解 所以 最优装在问题具有贪心选择性质 屁秸啸拷馅唐米刀蝇歧恫醚释男征剔迪洋柜霍