程序员必须会的基本算法1-动态规划算法(以经典的01背包问题为例)

先说01背包问题的背景:现在有一个背包,容量是4,物品有三个,重量和价格如下

现在要求将物品装入,使背包价值最大,但是每一样物品不能重复装,而且不能超出背包容量.

这里就需要用到动态规划算法,需要创建一个二维数组

数组的行表示背包的容量,最大是4,我们从0开始算,放入什么使背包价值最大,

数组的列表示可以放入背包的物品,只要在这一行的上面,都是可以放入背包的物品

先定义value数组是物品的价值,weight数组是物品的大小,size表示背包的容量

下面有这样的规律:

arr[i][0]=arr[0][j]=0; 

就是表格的第一行和第一列都是0,第一行表示没有物品可以放,第一列表示背包的容量是0

当weight[i]>size时:arr[i][j]=arr[i-1][j]

这个就是下一个商品可以加入背包的时候,如果这个商品的容量大于现在背包假设的容量,就直接采取上一个的装包方法

当weight[i]<=size时:arr[i][j]=max(arr[i-1][j]   ,value[i]+arr[i-1][size-weight[i])

package basic;

public class Dynamic
{
  /*
   * 动态规划算法(Dynamic Programming),核心是:大问题划分成小问题进行解决,从而一步步获得最优解
   * 和分治算法相似:其基本思想也是将要求解的问题分成若干个子问题,求解子问题,
   *          然后从这些子问题的解得到原问题的解
   *        不同的是:动态规划如其名,分解出来的子问题不是相互独立的,下一个子问题的求解是建立在
   *          上一个子问题的最优解的基础之上的
   * 和动态规划算法相关的经典问题是背包问题:
   * 是指一个指定容量的背包,若干具有一定价值和重量的物品,如何选择物品放入背包,
   * 使背包的物品价值最大,但是 又不能超过背包的容量
   * 背包问题分为:
   *         01背包  :就是每一个物品只能放一个
   *         完全背包:每一种物品可以无限件可以用,可以转化成01背包求解
   */
  public static void main(String[] args)
  {
    //下面分别表示物品的价值,重量和包的大小
    int[] value  = {1500,3000,2000};
    int[] weight = {1   ,4   ,3   };
    int size=4;
    
    //进行动态规划找最大价值的arr数组和标记加入哪一件商品的path数组
    int[][] arr =new int[value.length+1][size+1];
    int[][] path=new int[value.length+1][size+1];
    
    //本来应该初始化arr的第一行和第一列,使他们都为0,但是默认就是0,所以不初始化了
    //下面进行动态规划,第一行和第一列可以直接跳过,
    //each代表的是每一个可以加入的商品,weig代表的是背包的假设容量
    for (int each = 1; each < arr.length; each++)
    {
      for(int weig=1 ;weig<arr[0].length ; weig++)
      {
        //如果要加入的商品的大小超过背包的假设容量,就直接采取上一级的方法
        if(weight[each-1]>weig)
        {
          arr[each][weig]=arr[each-1][weig];
        }
        else
        {
          //如果加入的商品小于或等于背包假设容量,就要就从两个值里面取最大的
          //一个是上一个方法的装包的价值,另外一个是这个新商品的价值加上剩下
          //容量可以装的商品的的最大价值
          if(arr[each-1][weig]<(value[each-1]+arr[each-1][weig-weight[each-1]]))
          {
            arr[each][weig]=(value[each-1]+arr[each-1][weig-weight[each-1]]);
            path[each][weig]=1;
          }
          else
          {
            arr[each][weig]=arr[each-1][weig];
          }
        }
      }
    }
    
    for(int i =0; i < arr.length;i++) 
    {
      for(int j = 0; j < arr[i].length;j++) 
      {
        System.out.print(arr[i][j] + " ");
      }
      System.out.println();
    }
    /*
     * 下面是处理到底是在背包里面加入了那几件物品的,
     * arr数组里面显然是内容值最大的就是最优的解,而且每一次arr里面的数值变大
     * 在path数组里面都有记录,有变大就记录1,所以我们就直接可以从path数组的后面
     * 开始找,因为arr里面数值大的在后面
     */
    int each=path.length-1;
    int weig=path[0].length-1;
    while(each>0&&weig>0)
    {
      if(path[each][weig]==1)
      {
        System.out.println("商品"+each+"放入");
        weig=weig-weight[each-1];
      }
      each--;
    }
  }
}