首页 > 代码库 > 最优决策问题

最优决策问题

删除中的最值问题

(1)整数删数字后的最小数:请在整数n = 83179254297017652删除9个数,使得余下的数字按照原次序组成最小的的新数。

设计要点:在整数n中删除s个数字后余下的数字按原来的次序组成一个新的正整数m对给定的n,s寻找一种方案使得组成的数字最小,操作数据可以是高精度数据,在这里采用字符串的输入方式,每次删除一个数字之后,选择一个使剩下的数,最小的数作为删除对象之所以选择这样的贪心的操作,是因为删除s个数字全局最优解包含删除一个数字子问题的最优解。
当s  = 1时在n中删除那个数字能达到最小的目的?从左向右每相邻的两个数字比较,若出现左边大于右边删除左边的大数字,若不是即所有的数字全部相同或者升序,删除右边的数字。当s>1时(同时也小于n)按照上述的操作一个一个的删除,删除一个达到最小后,再从串首开始同上逐个数字比较删除第2个,依次分解为s次操作完成。若删除的不到s个就出现没有左边的数字大于右边的数字,就停止操作,打印剩下串的左边的n.length-s个数字Java代码实现:

package demo1;import java.util.Scanner;public class Main {    /**     * 删除中的最值问题     * @param args     */        public static void main(String[] args) {            Scanner input = new Scanner(System.in);        String str = input.next();        char[]c = str.toCharArray();        int s = input.nextInt();        System.out.println("输入先后删除的元素:");        int x = 0;        int t=0;        int i=0;        while(s>x&&t==0)        {                        //出现递减删除递减的首个字符            if(c[i] > c[i+1])            {                System.out.print(c[i]+" " );                for(int k = i;k<=c.length-2-x;k++)                                    //删除一个数字后面的数字前移                    c[k] = c[k+1];                                                                                    x++;//x统计的是删除的数字的个数                i = -1;//从头开始查找递减区间                                                                                            }            //若以无递减区间t==1            if(i == c.length-x-2)            {                t = 1;            }                        i++;                    }        System.out.println();        //打印得到的最小的数        for(int j=0;j<=c.length-1-s;j++)        {            System.out.print(c[j]+"  ");        }                            }}

 

运行结果:

83179254297017652
9
输入先后删除的元素:
8 3 9 7 5 4 9 7 2
1 2 0 1 7 6 5 2

最优决策问题