背包（动态规划）

一、01背包问题（特点：每件物品仅有一件，可以选择放与不放）

   有  件物品和一个容量为  的背包。第  件物品的费用是  ，价值是 。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

      用子问题定义状态：  f[i][v]=max(f[i-1][v],f[i-1]][v-c[i]]+w[i]);

      注意  有意义当且仅当存在一个前i件物品的子集，其费用总和为  。所以按照这个方程递推完毕后，最终的答案并不一定是  ，而是  的最大值。如果将状态的定义中的“恰”字去掉，在转移方程中就要再加入一项  ，这样就可以保证  就是最后的答案。

       1）初始化  memset(f,0,sizeof f)

       2)   优化（空间优化）

              第一种：滚动数组优化(当前状态只与前一状态有关）

//f[2][N]
     for (int i=1; i<=n; i++)
        {
            int v,w;
            cin>>v>>w;
            for (int j=0; j<=V; j++)
            {
                if(j2][j]=f[(i-1)%2][j]; //背包放不下（作用是防越界）
                else f[i%2][j]=max(f[(i-1)%2][j],f[(i-1)%2][j-v]+w);//滚动数组优化（这里是从i=1开始的，所以不会出现i-1<0的情况，不会出现负数%2的情况）
                //当前状态只与前一状态有关，所以求当前状态只需要存储前一状态。一个数对循环长度取余，则对于n长度的环，第n-1个的下一个将会是0，从而实现了循环。
                //当i=1时，i-1=0,此时(i-1)%2=0,i%2=1;   这时0，1都占满了，在求下一位数0这个位置时就用不到这一位0这个位置的数了，所以用它存储下一位的数，这样就达到了滚动效果。
                //当i=2时，i-1=1,此时(i-1)%2=1,i%2=0;
                //... ...
                //... ...
                //当i为奇数时，i-1=偶数，此时(i-1)%2=0,i%2=1；
                //当i为偶数时，i-1=奇数，此时(i-1)%2=1,i%2=0；
            }
        }
     printf("%d\n",f[n%2][V]);
     //滚动数组只能节约空间复杂度，时间复杂度和原来一样

            第二种：降维优化

//f[N]
for (int i=1; i<=n; i++)
        {
            int v,w;
            cin>>v>>w;
            for (int j=V; j>=v; j--)  //(从后往前)（防越界）
//降维：第i个物体的更新，只依赖于第i-1个的物体的结果，所以可以用滚动数组，每次只存i和i-1时候的值。第i个物体在容积为j状态的更新，只依赖i-1物体容量里j-v[i]的状态的结果。
  所以，从后面开始向前更新，则求j位置时候，j-v[i]的值依旧为i-1时候的值。
            {
                f[j]=max(f[j],f[j-v]+w);
            }
        }
        printf("%d\n",f[V]);

       3）越界(枚举容量时要求不超过背包容量，如果超过就意味着背包装不下第i个物品）

       4）时间复杂度O（N*V） 空间复杂度O（V）

二、完全背包（特点：与01背包不同的是物品有无限个）

// 递推公式计算时，f[i][j] = max{f[i-1][j], (f[i][j-v[i]]+w[i])}，注意这里当考虑放入一个物品 i 时应当考虑还可能继续放入 i，因此这里是f[i][j-v[i]]+w[i], 而不是f[i-1][j-v[i]]+w[i]。


降维优化后：
       for (int i=1; i<=n; i++)
        {
            for (int j=0; j<=V; j++) //和01背包不同，这里是从小到大枚举的，j-v[i]比j先算
            {
                if (j//这里是f[j]而不是f[j-1]
                else f[j]=max(f[j],f[j-v[i]]+w[i]);    //这里是f[j]而不是f[j-1]
            }
        }
        printf("%d\n",f[V]);