devbox
煮酒与君饮
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

算法设计与分析结课论文_算法设计与分析论文

作者：煮酒与君饮 | 2024-07-27 16:53:10

赞

踩

算法设计与分析论文

1背包问题

1.1基于动态规划的01背包问题算法实现

问题描述：

动态规划算法实现（Java）：

  1. import java.util.Scanner;
  2.  
  3. public class Packageof01 {
  4.     public static void main(String[] args) {
  5.         Scanner sc = new Scanner(System.in);
  6.         //m为背包总容量，n为物品数量。
  7.         int m = sc.nextInt();
  8.         int n = sc.nextInt();
  9.         /*
  10.         carry数组:动态规划得到的最优方案
  11.         weight数组:各个物品的重量
  12.         value数组:每个物品的价值
  13.         result:背包能装下的最大价值
  14.          */
  15.         int[][] carry = new int[n+1][m+1];
  16.         int[] weight = new int[n+1];
  17.         int[] value = new int[n+1];
  18.         //输入每个物品的重量、价值。
  19.         for (int i = 1; i <= n; i++) {
  20.             weight[i] = sc.nextInt();
  21.             value[i] = sc.nextInt();
  22.         }
  23.         //按物品重量与背包容量升序，按照当前容量能装下当前物品的最大价值，
  24.         // 更新carry数组（物品重量与背包容量向下兼容）。
  25.         for (int i = 1; i <= n; i++) {
  26.             for (int j = 1; j <= m; j++) {
  27.                 if (weight[i] > j)
  28.                     carry[i][j] = carry[i - 1][j];
  29.                 else {
  30.                     carry[i][j] = Math.max(carry[i - 1][j], value[i] + carry[i - 1][j - weight[i]]);
  31.                 }
  32.             }
  33.         }
  34.         //输出最优解
  35.         /*10 4
  36.         2 1
  37.         3 3
  38.         4 5
  39.         7 9*/
  40.         for(int i=0; i<=n;i++){
  41.             for(int j=0; j<=m;j++){
  42.                 System.out.print(carry[i][j]+" ");
  43.             }
  44.             System.out.println();
  45.         }
  46.         System.out.println("在背包容量为"+m+"的情况下，"+"所能装下物品的最大价值为："+carry[n][m]);
  47.     }
  48. }

代码运行结果：

  1. 0 0 0 0 0 0 0 0 0 0 0 
  2. 0 0 1 1 1 1 1 1 1 1 1 
  3. 0 0 1 3 3 4 4 4 4 4 4 
  4. 0 0 1 3 5 5 6 8 8 9 9 
  5. 0 0 1 3 5 5 6 9 9 10 12 
  6. 在背包容量为10的情况下，所能装下物品的最大价值为：12

时间复杂度：O（n^2）

1.2 基于贪心算法实现的部分背包问题

问题描述：对于每一个物品，可以选择放入物品全部或者物品的一部分，这种情况下选择物品的价值/物品的重量作为权重，按照权重将物品降序排序，首先放入权重最大的物品，直到不能完全放入一个物品，此时放入该物品的一部分。

贪心算法代码实现（Java）：

  1. import java.util.Scanner;
  2.  
  3. public class Package0fpart {
  4. //创建物品类，包括物品重量、价值、是否全部放入背包、物品的权重(p=value/weight)
  5.  
  6.     public static class goods {
  7.         int weight;
  8.         int value;
  9.         float n;
  10.         float p;
  11.     }
  12.  
  13.     public static void Greedy(goods[] a, int n, int v) {
  14.         for (int i = 0; i < n; i++) {
  15.             if (v > a[i].weight) { //当物品能放入背包时，将物品全部放入背包
  16.                 a[i].n = 1;
  17.                 v -= a[i].weight;
  18.  
  19.             } else if (v > 0) {//当物品无法全部放入背包时，放入一部分物品
  20.                 a[i].n = (float) v / a[i].weight;
  21.                 v = 0;
  22.             }
  23.         }
  24.     }
  25.  
  26.     //插入排序算法实现物品排序
  27.     public static void sort(goods[] arr) {
  28.         if (arr.length >= 2) {
  29.             for (int i = 1; i < arr.length; i++) {
  30.                 //挖出一个要用来插入的值，同时位置上留下一个可以存新的值的坑
  31.                 goods x = arr[i];
  32.                 int j = i - 1;
  33.                 //在前面有一个或连续多个值比x大的时候，一”直循环往前面找,将x插入到这串值前面
  34.                 while (j >= 0 && arr[j].p < x.p) {
  35.                     //当arr[j]比x小的时候，将j向后移一位，正好填到坑中
  36.                     arr[j + 1] = arr[i];
  37.                     j--;
  38.                     //将x插入到最前面
  39.                     arr[i + 1] = x;
  40.                 }
  41.             }
  42.         }
  43.     }
  44.  
  45.     public static void main(String[] args) {
  46.         Scanner sc = new Scanner(System.in);
  47.         System.out.println("请输入物品数量及背包容量:");
  48.         int n = sc.nextInt();
  49.         int v = sc.nextInt();
  50.         goods[] a = new goods[n]; //创建goods类数组并实例化
  51.         for (int i = 0; i < n; i++)
  52.             a[i] = new goods();
  53.         for (int i = 0; i < n; i++) {
  54.             System.out.println("请输入第" + (i + 1) + "个物品的重量及价值: ");
  55.             a[i].weight = sc.nextInt();
  56.             a[i].value = sc.nextInt();
  57.             a[i].p = (float) a[i].value / a[i].weight;
  58.         }
  59.         sort(a);
  60.         Greedy(a, n, v);
  61.         int sumOfvalue = 0;
  62.         int sumOfweight = 0;
  63.         for (int i = 0; i < n; i++) {
  64.             if (a[i].n == 0.0)
  65.                 break;
  66.             sumOfweight += (a[i].weight * a[i].n);
  67.             sumOfvalue += (a[i].value * a[i].n);
  68.             System.out.println("装入背包的第" + (i + 1) + "个物品为: ");
  69.             System.out.println("重量: " + a[i].weight + "价值:" + a[i].value + "完整 / 部分:" + a[i].n);
  70.             System.out.println("背包装入的总价值: " + sumOfvalue);
  71.             System.out.println("背包装入的总重量:" + sumOfweight);
  72.         }
  73.     }
  74. }

程序运行结果：

  1. 请输入物品数量及背包容量:
  2. 3
  3. 50
  4. 请输入第1个物品的重量及价值: 
  5. 10
  6. 60
  7. 请输入第2个物品的重量及价值: 
  8. 20
  9. 100
  10. 请输入第3个物品的重量及价值: 
  11. 30
  12. 120
  13. 装入背包的第1个物品为: 
  14. 重量: 10 价值:60 完整 / 部分:1.0
  15. 背包装入的总价值: 60
  16. 背包装入的总重量:10
  17. 装入背包的第2个物品为: 
  18. 重量: 20 价值:100 完整 / 部分:1.0
  19. 背包装入的总价值: 160
  20. 背包装入的总重量:30
  21. 装入背包的第3个物品为: 
  22. 重量: 30 价值:120 完整 / 部分:0.6666667
  23. 背包装入的总价值: 240
  24. 背包装入的总重量:50
  25.  
  26. 进程已结束,退出代码0

时间复杂度：O（n）

1.3 基于动态规划实现的完全背包问题

问题描述：对于每一个物品，其数量是无限的，对于背包容量不同的情况下，对于同一个物品，考虑放入数量为k的不同价值情况（k=0、1、2...n），选择价值最大的放置情况更新最大价值数组，直到所有的物品均被选择过。

动态规划代码实现（Java）：

  1. import java.util.Scanner;
  2.  
  3.  
  4. public class PackageofAll {
  5.     public static void main(String[] args) {
  6.         Scanner sc = new Scanner(System.in);
  7.         int n = sc.nextInt();
  8.         int m = sc.nextInt();
  9.         int[][] f = new int[n + 1][m + 1]; // f数组表示物品数量为i、背包容量为j的情况下的最大价值
  10.         int[] v = new int[n]; // n个物品的体积
  11.         int[] w = new int[n]; // n个物品的价值
  12.         int a = 0;
  13.         while (sc.hasNextLine() && a != n) {
  14.             v[a] = sc.nextInt();
  15.             w[a] = sc.nextInt();
  16.             a++;
  17.         }
  18.         for (int i = 1; i <= n; i++) {
  19.             for (int j = 0; j <= m; j++) {
  20.                 for (int k = 0; k * v[i - 1] <= j; k++) {
  21.                     f[i][j] = f[i - 1][j]; // 当背包放不下当前物品时，f取不放入该物品时的最大价值
  22.                     if (j >= v[i - 1])     // 当背包能放下当前物品时，考虑不放入该物品与放入该物品之间的最大值
  23.                         f[i][j] = Math.max(f[i - 1][j], f[i - 1][j - k * v[i - 1]] + k * w[i - 1]);
  24.                 }
  25.             }
  26.         }
  27.         for (int i = 0; i <= n; i++) {
  28.             for (int j = 0; j <= m; j++) {
  29.                 System.out.print(f[i][j] + " ");
  30.             }
  31.             System.out.println();
  32.         }
  33.         System.out.println(f[n][m]); //f数组最后一位为所有情况下的最大价值，因为背包容量越大，背包容纳的价值也越大。
  34.     }
  35. }

程序运行结果：

  1. 3
  2. 4
  3. 1 15
  4. 3 20
  5. 4 30
  6. 0 0 0 0 0 
  7. 0 15 30 45 60 
  8. 0 15 30 45 60 
  9. 0 15 30 45 60 
  10. 60
  11.  
  12. 进程已结束,退出代码0

时间复杂度：O（n^3）

2 针对背包问题的动态规划算法优化

2.1 针对01背包问题的一维数组优化

问题描述：对于01背包问题，可以考虑将二维结果数组变为一维数组，数组下标表示背包容量，数组数值表示该背包容量下的最大价值，代码改进如下：

  1. import java.util.Scanner;
  2.  
  3. public class Packageof01 {
  4.     public static void main(String[] args) {
  5.         Scanner sc = new Scanner(System.in);
  6.         //m为背包总容量，n为物品数量。
  7.         int m = sc.nextInt();
  8.         int n = sc.nextInt();
  9.         /*
  10.         carry数组:动态规划得到的最优方案
  11.         weight数组:各个物品的重量
  12.         value数组:每个物品的价值
  13.         result:背包能装下的最大价值
  14.          */
  15.         int[] carry = new int[m + 1];
  16.         int[] weight = new int[n + 1];
  17.         int[] value = new int[n + 1];
  18.         //输入每个物品的重量、价值。
  19.         for (int i = 1; i <= n; i++) {
  20.             weight[i] = sc.nextInt();
  21.             value[i] = sc.nextInt();
  22.         }
  23.         //按物品重量与背包容量升序，按照当前容量能装下当前物品的最大价值，
  24.         // 更新carry数组（物品重量与背包容量向下兼容）。
  25.         for (int i = 0; i <= n; i++) {
  26.             for (int j = m; j >= weight[i]; j--) {
  27.                 // 背包容量逆序遍历，防止重复选取物品，j>=物品重量，过滤掉放不下的情况
  28.                 carry[j] = Math.max(carry[j], value[i] + carry[j - weight[i]]);
  29.             }
  30.         }
  31.  
  32.         for (int j = 0; j <= m; j++) {
  33.             System.out.print(carry[j] + " ");
  34.         }
  35.         System.out.println();
  36.         System.out.println("在背包容量为" + m + "的情况下，" + "所能装下物品的最大价值为：" + carry[m]);
  37.     }
  38. }

程序运行结果：

  1. 10 4
  2. 2 1
  3. 3 3
  4. 4 5
  5. 7 9
  6. 0 0 1 3 5 5 6 9 9 10 12 
  7. 在背包容量为10的情况下，所能装下物品的最大价值为：12
  8.  
  9. 进程已结束,退出代码0

时间复杂度：O（m*n）

2.2 针对完全背包问题的一维数组优化

与01背包问题类似，可以考虑用一维数组压缩空间，与01背包不同的是，完全背包的背包容量需要顺序遍历，用到当前物品的不同数量已经考虑过的情况。程序实现如下：

  1. import java.util.Scanner;
  2.  
  3.  
  4. public class PackageofAll {
  5.     public static void main(String[] args) {
  6.         Scanner sc = new Scanner(System.in);
  7.         int n = sc.nextInt();
  8.         int m = sc.nextInt();
  9.         int[] f = new int[m + 1]; // f数组表示物品数量为i、背包容量为j的情况下的最大价值
  10.         int[] v = new int[n]; // n个物品的体积
  11.         int[] w = new int[n]; // n个物品的价值
  12.         int a = 0;
  13.         while (sc.hasNextLine() && a != n) {
  14.             v[a] = sc.nextInt();
  15.             w[a] = sc.nextInt();
  16.             a++;
  17.         }
  18.         for (int i = 1; i <= n; i++) {
  19.             for (int j = v[i-1]; j <= m; j++) {
  20.                 // 背包容量从能放下物品开始遍历，降低时间复杂度
  21.                 f[j] = Math.max(f[j], f[j - v[i - 1]] + w[i - 1]);
  22.             }
  23.         }
  24.         for (int j = 0; j <= m; j++) {
  25.             System.out.print(f[j] + " ");
  26.         }
  27.         System.out.println();
  28.         System.out.println(f[m]); //f数组最后一位为所有情况下的最大价值，因为背包容量越大，背包容纳的价值也越大。
  29.     }
  30. }

程序运行结果：

  1. 3
  2. 4
  3. 1 15
  4. 3 20
  5. 4 30
  6. 0 15 30 45 60 
  7. 60
  8.  
  9. 进程已结束,退出代码0

时间复杂度：可以看到，经过一维数组优化的算法，只需两次遍历就能求得最大价值，并且背包容量从能放下物品的容量开始遍历，所以总体时间复杂度为：O（m*n）

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/煮酒与君饮/article/detail/890976
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号