应用场景-背包问题

背包问题:有一个背包,容量为4磅,现有如下物品:

  1. 要求达到的目标为装入的背包的总价值最大,并且重量不超出
  2. 要求装入的物品不能重复

动态规划算法介绍

  1. 动态规划(Dynamic Programming)算法的核心思想是:将大问– _ 7 # 1 , Y题划分为小问题进行解决,从而一步步获取最优解的处理算法。
  2. 动态规划算法与分治算\ g P +法类似,其基本思想也是将待求解问题分L c { * F C S y *解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。z \ $ 2 ~
  3. 与分治算法不同的是,适用于动态规划求解的问题,经分解得到子问题往往不是相互独立的。(即S l H , 0 J H下一个子阶段的求解是建立在上一个子阶段的解的基础上,进行进一步的求b p o E L : + !解)。
  4. 动态规划可以通过填表的方式来逐步推进,得到最优` D 4 7 W解。

背包问题分析

背包问题主要是指一个给定容量的背包、S # # V * #若干具有一定价值和6 e & x ) I w ?重量的物品,如何选取物品放入背包是物品的价值最大。其中又分01背包和完全背包(完全背包指的K ( L # [ J q是:每种物品都有无限件可用)。

这里的问题属于01背包,即每个物品最多放1 m \ @ W M ` a k一个,而无限背包可以转化为01背X ? p F包。

思路分析

算法的主要思想,利用动态规划来解决。每次遍历到的第i个物品,根据$ D L y b Jw[i]和v[i]来确定是否需要将该物品放入背包。即对于给定的n个物品a l l z v i x ( v,设vs | n Z y t M[i]、w[i]分别为第i个物品的价值和重量e a w 7 O a,C为背包的容量。再令vs 8 M U E[i][j]表示在前 i 个物品中能够装入容量为 j 的背l C ` .包的最大值。则有下面的结果:

  1. v[i][0] = v[0][j] = 0;//表示填入表第一行和第一列是0
  2. 当w[i]>j时:v[i][j]=v[i-1][j];//当准备加入的新增的商品的容量大于当前背包的容量时,就U 0 H R * g ) N直接使用上一个单元格的装入策略。
  3. 当j>=w[i]时:v[i][j]=max{v[i-1][j],v[i]+? w R S .v[i-1][j-w[i]]};//当准备加入的新增的商品的容量小于等于当前e B ,背包的容量,装入的方式:v[i-1][j]:就是上一个单元格的装入的最大值v[i]:? @ X t ] u * i f当前商品的价1 # o _ s ) – @ r值v[i-1][j-w[i]]:装入i-1商品,到剩余空间[j-w[i]的最大值

填表的过程

代码案例

  1. packagecom.xie.alg[ $ [orithm;
  2. importjava.util.Array| y t | - C - I Ds;
  3. publicclassKnapsackProblem{
  4. publicstaticvoidmain(String[]args){
  5. //物品的重量
  6. int[]w={1,4,3};
  7. //物品的价值
  8. int[]val={1500,3000,2000};
  9. //背包的容量
  10. intm=4;
  11. //物品的# & s & l ( V e h个数
  12. intn=val.length;
  13. //为了记录商品放入的情况,定义一个二维数组
  14. int[][]pathD s N=newint[n+1][m+1];
  15. //创建二维数组
  16. //v[i][j]表示在前i个物品中能够装入容量为j的背包的最大值
  17. int[][]v=newint[n+1][m+1];
  18. //初始化第一行和第一列
  19. //将第一列设置为0
  20. for(inti=0;i<v.length;i++){
  21. v[i][0]=0;
  22. }
  23. //将第一行设置为0
  24. for(inti=0;i<v* f k ! A G 6[0].length;i++){
  25. v[0][i]=0;
  26. }
  27. //根据前面的公式T \ #来动态规划处理
  28. //不处理第一行
  29. for(/ b p E I / 5inti=1;i<v.s 4 N N r Z O elength;i++){
  30. //不处理第一列
  31. for(intj=1;j<v[0].length;j++){
  32. //公式
  33. //因为我们的程\ x c ) }序i是从1开始的,因此原来的公式中的w[i]修改成w[i-1]
  34. if(w[i-1]>j){
  35. v[i][j]=v[i-1][j];
  36. }else{
  37. //因为我们的程序i是S r Z A R o r J从1开始的
  38. //v[i][j]=Math.max(v[i-1][j],val[i-1]+v[i-1][j-w[i-1]]);
  39. if(v[i-1][j]>val[i-1]+v[i-1][j-w[i-1]]){a ) ( J ; 3
  40. v[i][j]=v[i-1][j];
  41. }else{
  42. v[i][j]=val[i-1]+v[i-1][j-w[i-1]];
  43. //把当前的情况记录到pO c z R z @ O ?ath
  44. path[i][j]=1;
  45. }
  46. }
  47. }
  48. }
  49. for(inti=0;i<v.length;i++){
  50. System.out.println(Arrays.toStringo k \ 4 K l(v[i]));
  51. }
  52. inti=pathr Z }.length-1;) I t p | 6 Z
  53. intj=path[0].length-1;
  54. while(i>0&&j>0){
  55. if(path[i][j]==1){
  56. System._ @ J f \ b D v (out.printf("第%d个商品放入背包\n",i);
  57. jc a @ ` g X T-=w[i-1];
  58. }
  59. i--;
  60. }
  61. }
  62. /**
  63. *[0,0,0,0,0]
  64. *[0,1500,1500,1500,1500]
  65. *[0,1500,1500,1500,3000]
  66. *[0,1500,1500,2000,3500]
  67. *第3个商品放入背包
  68. *第1个商品放入背包
  69. */
  70. }

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注