动态规划（五）背包问题

基本思想：
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。

应用场景：
　　动态规划求解具有以下的性质：
　　最优子结构性质、子问题重叠性质　　
　　最优子结构性质：最优解包含了其子问题的最优解，不是合并所有子问题的解，而是找最优的一条解线路，选择部分子最优解来达到最终的最优解。
　　子问题重叠性质：先计算子问题的解，再由子问题的解去构造问题的解（由于子问题存在重叠，把子问题解记录下来为下一步使用，这样就直接可以从备忘录中读取）。其中备忘录中先记录初始状态。

2、求解思路

　　①、将原问题分解为子问题（子问题和原问题形式相同，且子问题解求出就会被保存）；
　　②、确定状态：01背包中一个状态就是NN个物体中第ii个是否放入体积为VV背包中；
　　③、确定一些初始状态（边界状态）的值；
　　④、确定状态转移方程，如何从一个或多个已知状态求出另一个未知状态的值。（递推型）

01背包问题求解思路

　　①、确认子问题和状态
　　01背包问题需要求解的就是，为了体积V的背包中物体总价值最大化，NN件物品中第ii件应该放入背包中吗？（其中每个物品最多只能放一件）
　　为此，我们定义一个二维数组，其中每个元素代表一个状态，即前ii个物体中若干个放入体积为VV背包中最大价值。数组为：f[N][V]f[N][V]，其中fijfij表示前ii件中若干个物品放入体积为jj的背包中的最大价值。
　　②、初始状态
　　初始状态为f[0][0−V]f[0][0−V]和f[0−N][0]f[0−N][0]都为0，前者表示前0个物品（也就是空物品）无论装入多大的包中总价值都为0，后者表示体积为0的背包啥价值的物品都装不进去。
　　③、转移函数

if (背包体积j小于物品i的体积)
    f[i][j] = f[i-1][j] //背包装不下第i个物体，目前只能靠前i-1个物体装包
else
    f[i][j] = max(f[i-1][j], f[i-1][j-Vi] + Wi)

　　最后一句的意思就是根据“为了体积V的背包中物体总价值最大化，NN件物品中第ii件应该放入背包中吗？”转化而来的。ViVi表示第ii件物体的体积，WiWi表示第ii件物品的价值。这样f[i-1][j]代表的就是不将这件物品放入背包，而f[i-1][j-Vi] + Wi则是代表将第i件放入背包之后的总价值，比较两者的价值，得出最大的价值存入现在的背包之中。

#include<iostream>
using namespace std;

int main()
{
    int nArr[6][13] = {{0}};
    int nCost[6] = {0 , 2 , 5 , 3 , 10 , 4};  //花费
    int nVol[6]   = {0 , 1 , 3 , 2 , 6 , 2}; //物体体积
    int bagV = 12;

    for( int i = 1; i< sizeof(nCost)/sizeof(int); i++)
    {
        for( int j = 1; j<=bagV; j++)
        {
            if(j<nVol[i])
                nArr[i][j] = nArr[i-1][j];
            else
                nArr[i][j] = max(nArr[i-1][j] , nArr[i-1][j-nVol[i]] + nCost[i]);       
            cout<<nArr[i][j]<<' ';
        }   
        cout<<endl;
    }
    cout<<nArr[5][12]<<endl;

    return 0;
}

01背包问题其实就可以化简为涂写下面的表格，其中每个数对应数组nArr中每个元素，初始化部分为0，然后从左上角按行求解，一直求解到右下角获取最终解nArr[5][12]。