动态规划典型应用：背包问题

动态规划算法简要介绍：

动态规划算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获得最优解的处理算法。

动态规划算法与分治算法类似，其基本思想也是将待求解问题分解为若干个子问题，然后从这些子问题的解获得原问题的解，与分治算法不同的是，适用于动态规划算法的问题，经分解得到的子问题往往不是相互独立的
（即下一个子阶段的问题求解建立在新的子阶段解的基础上）

问题描述：

给定一个定容量的背包，和若干有一定价值和重量的物品，求背包可装物品的最大价值

背包问题分为0/1背包（背包中放置的物品不可以重复）和完全背包（背包中放置的物品可以重复）。

本文求解的是0/1背包的最优解。

思路分析：

• 每一个物品放入背包时有三种情况：

? 1.其重量大于背包容量，不可以放入背包：

? 2.其重量小于背包余量，可以放入背包：

? 3.其重量大于背包容量小于背包余量：此时又分两种情况

? 3.1从背包中取出一个物品，放入此物品

? 3.2不放入此物品

? 注：背包容量为给定的背包空间大小；背包余量为背包容量减去背包中已有物品重量的剩余空间

• 当我们将物品放入背包时，发生上述第三种情况时，我们需要比较第三种情况再次产生的两种可能那种会使得背包所装物品的价值最大。
• 此时对3.1的求解为：此物品的价值加上背包容量减去此物品的重量所剩空间可以装除过此物品的其他物品的最大价值。
• 因此，我们必须求出背包容量在小于其定容量的每种情况的最优解，以防之后求最终背包容量可装物品最大价值时会用到。

公式提炼：

将要放入背包的商品排成一竖列（1，2，3，4……）作为二维表的每一行的头部内容，（1，2，3，4……n）为逐步增大的背包容量，直至给定的固定容量。作为二维表的每一列的头部内容。根据物品的重量和价值选择性的将物品放入背包。

v[i] [j]：前i个物品中能够装入容量为j的背包的最大价值（二维数组的不同列为不断变大的背包容量，数组的不同行表示不同的物品）
w[i]：第i个物品的重量
v[i]：第i个物品的价值
$$
<1> v[i][0]=v[0][i]=0
$$

$$
<2>当w[i]>j时，v[i][j]=v[i-1][j];
$$

$$
<3>当w[i]<=j时，v[i][j]=max{ v[i-1][j] , v[i-1][j-w[i]] + v[i] }
$$

1. 第一个公式：数组的下标从0开始;前0个物品，或容量为0的背包所对应的值都为0

2. 第二个公式：当第i个物品的重量大于背包时，此时容量为j背包的最优解为前i-1个物品中能够装入容量为j的背包的最大价值。

3. 第三个公式：当第i个物品的重量大于背包时，此时背包价值最优解有两种可能：
   （1）第i个商品不放入背包中：此时容量为j背包的最优解为，前i-1个物品中能够装入容量为j的背包的最大价值。

   （2）第i个商品放入背包中：此时容量为j背包的最优解为，当前商品价值 加上 当前背包容量减去当前商品重量的剩余余量能够装入前i-1个商品的最大价值。

   举例说明

   给定背包容量为4kg，
   给定商品：吉他：重量：1kg,价值：1500元
   音响：重量：4kg，价值： 3000元
   电脑：重量：3kg, 价值：2000元

   二维表呈现：

   物品	1kg	2kg	3kg	4kg
   	0	0	0	0
   吉他	0	1500	1500	1500
   音箱	0	1500	1500	3000
   电脑	0	1500	2000	3500

代码实现：

/**
 *
 * @param values:物品的价值
 * @param weight：物品的重量     values与weight数组中的值一一对应。
 * @param space：背包可装重量
 * 输出最优解，背包装那几个物品？背包可装物品的最多价值？
 * 要求：（0/1）背包中的物品不可重复
 */
public static void getMaxValue(int values[],int[] weight,int space){
    int[][] arr=new int[values.length+1][space+1];//行代表每一个物品，列代表背包的空间在逐步变大;加1是因为将0也算进去这
    int[][] path=new int[values.length+1][space+1];//用于记录物品放入背包
    for(int i=1;i< arr.length;i++){
        for(int j=1;jj){
                arr[i][j]=arr[i-1][j];
            }else {
                arr[i][j]=Math.max(arr[i-1][j],arr[i-1][j-weight[i-1]]+values[i-1]);
                if(arr[i-1][j]>arr[i-1][j-weight[i-1]]+values[i-1]){
                    arr[i][j]=arr[i-1][j];
                }else {
                    arr[i][j]=arr[i-1][j-weight[i-1]]+values[i-1];
                    path[i][j]=1;
                }
            }
        }
    }
    for(int i=0;i0 && j>0){//从path的最后开始找
        if(path[i][j]==1){
            System.out.println("将第"+i+"件物品放入背包");
            j-=weight[i-1];//放入一件物品后背包的容量将减少。
        }
       i--;//由于背包中不可以放置同一物品两次，故将i--；不再关注此物品
    }
    System.out.println("背包中可放物品最大值为："+arr[arr.length-1][arr[0].length-1]);
}