亲宝软件园·资讯

展开

Java背包问题

LNORA 人气:0

动态规划算法

动态规划算法的思想

动态规划算法处理的对象是多阶段复杂决策问题,动态规划算法和分治算法类似,其基本思想也是将待求解问题分解成若干个子问题(阶段),然后分别求解各个子问题(阶段),最后将子问题的解组合起来得到原问题的解,但是与分治算法不同的是,子问题往往不是相互独立的,而是相互联系又相互区别的

动态规划算法问题求解的目标是获取导致问题最优解的最优决策序列(最优策略)。对于一个决策序列,可以用一个数值函数(目标函数)衡量这个决策的优劣。

最优性原理

动态规划算法的最优性原理:一个最优决策序列具有这样的性质,不论初始状态和第一步决策如何,对前面的决策所形成的状态而言,其余的决策必须按照前一次决策所产生的新状态构成一个最优决策序列。

最优性原理体现为问题的最优子结构特性,对于一个问题,如果能从较小规模的子问题的最优解求得较大规模同类子问题的最优解,最终得到给定问题的最优解,也就是问题的最优解中所包含的子问题的最优解,这种性质被称为最优子结构性质。最优子结构特性使得在从较小问题的解构造较大问题的解时,只需考虑子问题的最优解,然后以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解,它保证了原问题的最优解可以通过求解子问题的最优解来获得,最优子结构的特性是动态规划算法求解问题的必要条件。

动态规划算法的三大特点

动态规划算法中的0/1背包问题

0/1背包问题的规则是不允许该物品进行拆分,即只有把物品放入和不放入两个基本状态,要使用动态规划算法求解决如何放物品才可以是背包中的物品的总价值达到最高。

示例

有一个载重为10的背包,现有4类物品,每类物品的重量分别为(w0,w1,w2,w3)=(2,3,4,7),它们的价值分别为(p0,p1,p2,p3)=(1,3,5,9)。试问如何装载能够使背包容纳物品的价值最大。

package 算法设计与分析;
 import java.util.Arrays;
 import java.util.Scanner;
 //m表示的是背包的容量,a表示有多少种类的物品,数组w用与存放每类物品的重量,数组val用于存放每类物品的价值
 public class my {
     public static void main(String[] args) {
         Scanner scanner = new Scanner(System.in);
         System.out.print("请输入背包的容量:");
         int m = scanner.nextInt();
         Scanner inScanner = new Scanner(System.in);
         System.out.print("请输入物品的个数:");
         int a = inScanner.nextInt();
         int[] w = new int[a + 1];
         System.out.print("请输入物品的重量:" + " ");
         for (int i = 1; i <= a; i++) {
             w[i] = inScanner.nextInt();
         }
         int[] val = new int[a+ 1];
         System.out.print("请输入物品的价值:" + " ");
         for (int i = 1; i <= a; i++) {
             val[i] = inScanner.nextInt();
         }
         int n = val.length;
         int[][] path = new int[n +1][m+1 ];
         //创建二维数组
         //v[i][j]:表示在前i个物品中能够装入容量为j的背包中的最大价值
         int[][] v = new int[n +1][m + 1];
         //初始化第一行和第一列
         for (int i = 0; i < v.length; i++) {//v.length:获取二维数组的行数
             v[i][0] = 0;//将第一列设置为0
         }
         for (int i = 0; i < v[0].length; i++) {//v[0].length:获取二维数组的列数
             v[0][i] = 0;//将第一行设置为0
         }
         for (int i = 1; i < v.length; i++) {//int i = 1 不处理第一行
             for (int j = 1; j < v[0].length; j++) {//int j = 1 不处理第一列
                 if (w[i - 1] > j) {
                     v[i][j] = v[i - 1][j];
                 } else {
                     if (v[i - 1][j] < (val[i - 1] + v[i - 1][j - w[i - 1]])) {
                         v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]];
                         //把当前情况记录到path
                         path[i][j] = 1;
                     } else {
                         v[i][j] = v[i - 1][j];
                     }
                 }
             }
         }
         //输出二维数组:
         for (int[] ints : v) {
             System.out.println(Arrays.toString(ints));
         }
         //输出最后我们是放入的那些商品
         int i = path.length - 1;//行的最大下标
         int j = path[0].length - 1;//列的最大下标
         while (i > 0 && j > 0) {//从path的最后开始找
             if (path[i][j] == 1) {
                 System.out.printf("第%d个商品放入背包\n", i-1);
                 j -= w[i - 1];
             }
             i--;
         }
     }
 }

输入一个背包容量为10,里面有4类物品,物品的重量分别为2,3,4,7,物品的价值分别为1,3,5,9

 结果 

动态规划算法的优点

若要解一个给定问题,我们需要解其不同部分(即子问题),再合并子问题的解以得出原问题的解。 通常许多子问题非常相似,为此动态规划法试图仅仅解决每个子问题一次,从而减少计算量: 一旦某个给定子问题的解已经算出,则将其记忆化存储,以便下次需要同一个子问题解之时直接查表。 这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

小结

以上就是针对动态规划算法的详细分析,利用动态规划算法可以避免重复计算多次子问题,提高效率,使计算机的性能更好!

加载全部内容

相关教程
猜你喜欢
用户评论