贪心和动态规划

public class CardDp {
    public static void main(String[] args) {
        int weigth[] = {1,2,3,4,5,9};    //购物车那个问题 只需要一个价值就行了，重量都都没有。
        int w = 8;
        int n = 6;
        int dp[][] = new int[n+1][w+1];        //n表示是物品，w表示重量,初始化全是0
        for(int i = 1; i<= n; i++){    //每次加的物品
            for(int cw = 1 ; cw <= w ; cw ++){        //分割的背包
                if(weigth[i - 1] <= cw){        //表示这个物品可以装进去
                    dp[i][cw] = Math.max(
                            weigth[i-1] + dp[i-1][cw-weigth[i-1]],
                            dp[i-1][cw]
                            );
                }else{
                    dp[i][cw] = dp[i-1][cw];    //不能装
                }
            }
        }
        System.out.println(dp[n][w]);
    }
}

public class Dp {
    public static void main(String[] args) {
        int value [] ={60,100,120};
        int weigth[] = {10,20,40};    //购物车那个问题 只需要一个价值就行了，重量都都没有。
        int w = 50;
        int n = 3;
        int dp[][] = new int[n+1][w+1];        //n表示是物品，w表示重量,初始化全是0
        for(int i = 1; i<= n; i++){    //每次加的物品
            for(int cw = 1 ; cw <= w ; cw ++){        //分割的背包
                if(weigth[i - 1] <= cw){        //表示这个物品可以装进去
                    dp[i][cw] = Math.max(
                            value[i-1] + dp[i-1][cw-weigth[i-1]],
                            dp[i-1][cw]
                            );
                }else{
                    dp[i][cw] = dp[i-1][cw];    //不能装
                }
            }
        }
        System.out.println(dp[n][w]);
    }
}

class Metting implements Comparable<Metting> {
    int meNum; // 编号
    int startTime; // 开始时间
    int endTime; // 结束时间
    public Metting(int meNum, int startTime, int endTime) {
        super();
        this.meNum = meNum;
        this.startTime = startTime;
        this.endTime = endTime;
    }
    public int compareTo(Metting o) {
        if (this.endTime > o.endTime)
            return 1;
        return -1;
    }
    @Override
    public String toString() {
        return "Metting [meNum=" + meNum + ", startTime=" + startTime
                + ", endTime=" + endTime + "]";
    }
}
public class MettingTest {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        List<Metting> mettings = new ArrayList<Metting>();
        int n = cin.nextInt();    //n个会议
        for (int i = 0 ;i < n; i++){
            int start = cin.nextInt();
            int end = cin.nextInt();
            Metting metting = new Metting(i+1, start, end);
            mettings.add(metting);
        }
        mettings.sort(null);
        int curTime = 0;        //当前的时间,从一天的0点开始,如果领导要求从8点开始 那curTime=8
        for(int i = 0 ; i < n; i ++){
            Metting metting = mettings.get(i);
            if(metting.startTime >= curTime){        //会议的开始时间比我们当前的要大 表示可以开
                System.out.println(metting.toString());
                curTime = metting.endTime;
            }
        }
    }
}

public class QuiklySort {
    public static void main(String[] args) throws Exception {
        //int data[] = { 4, 5, 6, 3, 2, 1 };
        String str = null;
        String fileName = "E:\\workspace\\sort\\200w.txt";
        InputStreamReader isr = new InputStreamReader(new FileInputStream(fileName), "UTF-8");
        BufferedReader br = new BufferedReader(isr);
        double data[] = new double[2100002];
        int i = 0;
        while ((str = br.readLine()) != null) {
            data[i++] = Double.valueOf(str);
        }
        System.out.println("数据读取完毕，size为" + i);
        long start = System.currentTimeMillis();
        qSort(data, 0, data.length - 1);
        /*File file =new File("E:\\workspace\\sort\\200w-qsort.txt");
        Writer out =new FileWriter(file);
        for(i = 0 ; i< data.length ; i++) {
            out.write(String.valueOf(data[i]) + "\r\n");
        }
        out.close();*/
        System.out.println("快排消耗的时间为:" + (System.currentTimeMillis() - start) + "ms");
        //System.out.println(Arrays.toString(data));
    }
    public static void qSort(double data[], int left, int right) {
        double base = data[left];
        int ll = left;
        int rr = right;
        while (ll < rr) {
            while (ll < rr && data[rr] >= base) {
                rr--;
            }
            if (ll < rr) {
                double temp = data[rr];
                data[rr] = data[ll];
                data[ll] = temp;
                ll++;
            }
            while (ll < rr && data[ll] <= base) {
                ll++;
            }
            if (ll < rr) {
                double temp = data[rr];
                data[rr] = data[ll];
                data[ll] = temp;
                rr--;
            }
        }
        if (left < ll - 1)
            qSort(data, left, ll - 1);
        if (ll + 1 < right)
            qSort(data, ll + 1, right);
    }
}