算法很美01背包问题动态规划、贪心

题目描述

• Sidney想去Gandtom家玩。但Sidney家和Gandtom家之间是高低不平、坑坑洼洼的土路。所以他需要用他的背包装几袋稀的泥，在路上铺平一些干的土，使路变成平整的泥土，才能到Gandtom家见到Gandtom。
  已知现在有n种稀的泥，第i种稀的泥的质量为wi，体积为vi。Sidney的包能装体积不超过V的稀的泥。Sidney出门时携带的稀的泥的质量应该尽可能的大。在此前提下，携带的稀的泥的体积也应该尽可能的大。
  试求Sidney最多能携带多少质量的稀的泥与此时的最大体积上路。
• Input
  第一行有一个整数T，表示组数。
  每组数据第一行有两个正整数n、V(0<n,V<=103) 。
  每组数据第二行有个n正整数，第i个数为wi(0<wi<=106)。
  每组数据第三行有个n正整数，第i个数为vi(0<vi<=103)
• Output
  每组样例第一行输出两个整数。表示Sidney最多能携带多少质量的稀的泥与此时的最大体积上路。
  Sample Input

2
5 3
1 2 3 4 5
1 1 1 1 1
3 7
1 2 1
3 5 3

Sample Output

12 3
2 6

题目解析

• 该题用贪心不好保证两个都最大，dp数组每个单元格表示，有j种水泥和i个背包容量的最优装载情况，在dp数组中可以通过dfs寻找每次“选择”的水泥（不过时间复杂度有些高）

代码

	        Scanner scanner=new Scanner(System.in);
	        int T=scanner.nextInt();

	        for (int i = 0; i < T; i  ) {

	            int n=scanner.nextInt();
	            Shuini[] samples=new Shuini[n];
	            int V=scanner.nextInt();
	            for (int j = 0; j < n; j  ) {
	                samples[j]=new Shuini(scanner.nextInt(),0);

	            }
	            for (int j = 0; j < n; j  ) {
	                samples[j].vi=scanner.nextInt();
	                samples[j].getUnitValue();
	            }
	            //贪心算法（无法保证w，v同时最大）
	            //solve(samples,V);

	            //dp动规划
	            solve1(samples,V);
	        }


	    }

	    private static void solve1(Shuini[] samples, int v) {
	        int[][]  dp=new int[samples.length][v 1];

	        //初始化dp
	        for (int i = 0; i < dp.length; i  ) {
	            //当背包没有容量的时候全部初始化为0
	            dp[i][0]=0;
	        }
	        boolean falg=false;
	        for (int i = 0; i < dp[0].length; i  ) {

	            if (falg) {
	                dp[0][i]= samples[0].vi;
	                continue;
	            }
	            if (i>=samples[0].vi) {
	                dp[0][i]= samples[0].vi;
	                falg=true;
	            }else {
	                dp[0][i]=0;
	            }

	        }

	        //获取最大质量
	        for (int i = 1; i < dp.length; i  ) {
	            for (int j = 1; j < dp[0].length; j  ) {
	                //当前背包装得下
	                if(j>=samples[i].vi) {
	                    int yao=samples[i].wi dp[i-1][j-samples[i].vi];
	                    int buyao=dp[i-1][j];
	                    dp[i][j]=max(yao,buyao);
	                }else {//当前背包装不下
	                    dp[i][j]=dp[i-1][j];
	                }
	            }
	        }

	        //dfs(samples,dp,0,0,0);
	        //获取背包装载最大v值

	        System.out.println(dp[dp.length-1][v]);

	    }

	    private static int dfs(Shuini[] samples,int[][] dp, int x, int y,int maxV) {



	        if(dp[x][y]==samples[x].wi) {
	            maxV =samples[x].vi;
	            return maxV;
	        }

	        for (int i =dp.length-1 ; i >=0; i  ) {
	            for (int j = dp[0].length-1; j >= 0; j  ) {
	                //有可能出现要的情况(出现选和没选答案相同的情况）
	                if(dp[x][y]-samples[x].wi-dp[x-1][y-samples[x].vi]==0) {
	                    maxV =samples[x].vi;
	                    int xuanle=dfs(samples,dp, x-1, y-samples[x].vi,maxV);
	                    //回溯；
	                    maxV-=samples[x].vi;

	                    int meixuan=dfs(samples, dp, x-1, y,maxV);

	                    maxV =max(xuanle,meixuan);
	                }
	            }
	        }
	        return maxV;




	    }

	    private static int max(int yao, int buyao) {
	        if (yao>=buyao) {
	            return yao;
	        }
	        return buyao;
	    }

	    //贪心算法，贪心失败//无法保持 质量和体积都最大
	    //仅能保持质量最大
	    private static void solve(Shuini[] samples,int V) {
	        int maxWeight=0;
	        int leftV=V;
	        Arrays.sort(samples);
	        Arrays.toString(samples);
	        for (int i = 0; i < samples.length; i  ) {
	            if (leftV==0) {
	                System.out.print(maxWeight " ");
	                System.out.println(V);
	                return;
	            }
	            if(samples[i].vi<=leftV) {
	                leftV-=samples[i].vi;
	                maxWeight =samples[i].wi;
	            }
	        }
	        System.out.print(maxWeight " ");
	        System.out.println(V-leftV);

	    }



	    private static class Shuini  implements Comparable<Shuini>{
	        int wi;
	        int vi;
	        int unitW;

	        private void getUnitValue() {
	            unitW = wi/vi;
	        }

	        //单位质量大的放前面，单位质量相同的，体积小的放后面
	        @Override
	        public int compareTo(Shuini o) {
	            if(this.unitW>o.unitW) {
	                return -1;
	            }else if (this.unitW==o.unitW) {
	                return (int) (o.vi-this.vi);
	            }else {
	                return 1;
	            }
	        }


	        public Shuini(int wi, int vi) {
	            super();
	            this.wi = wi;
	            this.vi = vi;

	        }

	        @Override
	        public String toString() {
	            return "Shuini [wi="   wi   ", vi="   vi   ", unitW="   unitW   "]";
	        }


	    }

这篇好文章是转载于：学新通技术网