实验五：0-1 背包问题的算法设计

学号:SA19225157

一、实验要求

算法设计： 输入物品数 n，背包容量 c，输入 n 个物品的重量、价值，在以上算法中任选两个实现 最优解决 0-1 背包问题。

请问：所选算法的实现流程图或者伪代码是什么？比较时间复杂度和空间复杂度，得出 什么结论？

1.动态规划方法算法的实现代码

语言：Java

public void dongtaiguihuapublic void dongtaiguihua(InputStream in)  {
        Scanner scanner = new Scanner(in);
        int n = scanner.nextInt();//物品数n
        int c = scanner.nextInt();//背包容量c
        int[] weights = new int[n + 1];
        int[] values = new int[n + 1];
        for (int j = 1; j <= n; j++) {
            int w = scanner.nextInt();
            int v = scanner.nextInt();
            weights[j] = w;
            values[j] = v;
        }
        int[][] dp = new int[n + 1][c + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= c; j++) {
                if (j < weights[i]){
                    dp[i][j] = dp[i - 1][j];
                }else{
                    dp[i][j] = Math.max(dp[i - 1][j],dp[i - 1][j - weights[i]] + values[i]);
                }
            }
        }
        System.out.println(dp[n][c]);
    }

2.贪心方法算法的实现代码

public void tanxinpublic void tanxin(InputStream in)  {
       Scanner scanner = new Scanner(in);
       int n = scanner.nextInt();//物品数n
       int c = scanner.nextInt();//背包容量c
       int[] weights = new int[n + 1];
       int[] values = new int[n + 1];

       List list = new ArrayList<>();
       for (int j = 1; j <= n; j++) {
           int w = scanner.nextInt();
           int v = scanner.nextInt();
           weights[j] = w;
           values[j] = v;
           double d = (double) v / (double) w;//计算单价
           Result result = new Result(d,j);
           list.add(result);
       }
       //排序，单价最高的在前面
       Collections.sort(list, new Comparator() {
           @Override
           public int compare(Result o1, Result o2) {
               if(o2.danjia - o1.danjia > 0){
                   return 1;
               }else if(o2.danjia - o1.danjia == 0){
                   return 0;
               }else{
                   return -1;
               }
           }
       });
       int sum = 0;
       int finalValue = 0;
       for (int i = 0; i < list.size(); i++) {
           int index = list.get(i).index;
           if (sum + weights[index] <= c){
               sum = sum + weights[index];
               finalValue += values[index];
           }
       }
       System.out.println(finalValue);
   }
   class Result{
       public double danjia;
       public int index;

       public Result(double danjia, int index) {
           this.danjia = danjia;
           this.index = index;
       }
   }

二、复杂度分析

n为物品数量，c为背包容量

	动态规划方法	贪心方法
时间复杂度	O(n * c)	O(nIgn)
空间复杂度	O(n * c)	O(n)

三、结论：

1. 对于0-1背包问题，贪心选择不一定能得到最优解是因为：它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。
2. 动态规划法可以完美解决0/1背包问题，得到最优解。