蓝桥杯算法提高VIP-01背包 （C++代码）

解题思路:

        不妨用子问题定义状态：即dp[i][j]表示前i件物品(部分或全部)恰放入一个容量为j的背包时可以获得的最大价值。则状态转移方程：dp[i][j]=max{dp[i-1][j],dp[i-1][j-w[i]]+v[i]}。通过递推完成问题求解。

        这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。

        解释“将前i件物品放入容量为j的背包中”这个子问题：若只考虑第i件物品放/不放，那么该子问题就可以转化为一个只牵扯前i-1件物品的问题。

        ① 如果不放第i件物品，问题就转化为“前i-1件物品放入容量为v的背包中”

        ② 如果放第i件物品，问题就转化为“前i-1件物品放入剩下的容量为j-w[i]的背包中”，此时能获得的最大价值就是f [i-1][v-w[i]]再加上通过放入第i件物品获得的价值c[i]。

注意事项:

以上方法的时间和空间复杂度均为O(nW)，其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到O(W)。

        先考虑上面的基本思路如何实现：

        肯定是有一个主循环i=1..N，每次算出来二维数组dp[i][0..W]的所有值。那么，如果只用一维数组dp[0..W]，能不能保证第i次循环结束后dp[W]中表示的就是我们定义的状态dp[i][j]呢？

        dp[i][j]是由dp[i-1][j]和dp[i-1][j-w[i]]两个子问题递推而来，能否保证在推dp[i][j]时（即在第i次主循环中推dp[j]时）能够得到dp[i-1][j]和dp[i-1][j-w[i]]的值呢？事实上，这要求在每次主循环中我们以j=W..0的逆序推dp[j]，这样才能保证推dp[j]时dp[j-w[i]]保存的是状态dp[i-1][j-w[i]]的值（即结果的“无后效性”）。

        代码实现如下：

        for(i=1;i<=N;i++)

                for(j=W;j>=w[i];j--)

                        dp[j]=max(dp[j],dp[j-w[i]]+v[i]);

        其中：dp[j]=max{dp[j], dp[j-w[i]]+v[i]}相当于转移方程dp[i][j]=max{dp[i-1][j],dp[i-1][j-w[i]]+v[i]}，因为现在的dp[j-w[i]]就相当于原来的dp[i-1][j-w[i]]。

        然而，如果将j的循环顺序从上面的逆序改成顺序的话，那么则成了dp[i][j]由dp[i][j-w[i]]推知，与本题意不符，但它却是另一个重要的完全背包问题最简捷的解决方案，故只用一维数组解01背包问题是十分必要的（特别是数据规模较大的时候，对空间复杂度的优化十分重要）。

参考代码://正确代码（经过空间优化）

#include<bits/stdc++.h>

using namespace std;

const int maxn=20000;

int n,m,w[maxn],v[maxn],dp[maxn];

int main()

{

    int i,j;

    cin>>n>>m;

     for(i=1;i<=n;i++)

         cin>>w[i]>>v[i];

     for(i=1;i<=n;i++)

          for(j=m;j>=w[i];j--)

              dp[j]=max(dp[j],dp[j-w[i]]+v[i]);//转移方程

     cout<<dp[m]<<endl;

     return 0;

}

//错误代码（内存超限）

#include<bits/stdc++.h>

using namespace std;

const int maxn=20000;

int n,m,w[maxn],v[maxn],dp[maxn][maxn];

int main()

{

     int i,j;

     cin>>n>>m;

     for(i=1;i<=n;i++)

         cin>>w[i]>>v[i];

     for(i=1;i<=n;i++)

           for(j=m;j>=1;j--)

              if(j>=w[i])

                 dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);//转移方程

              else

                 dp[i][j]=dp[i-1][j];

     cout<<dp[n][m]<<endl;

     return 0;

}