背包学习之背包九讲

做了一些icpc题目，感受到动态规划的重要性，在此学习背包
参考至博客背包九讲

背包九讲

01背包问题
完全背包问题
多重背包问题
混合背包问题
二维费用的背包问题
分组背包问题
有依赖的背包问题
背包问题求方案数
求背包问题的具体方案

01完全背包：

问题：n个物品(体积和价值分别为v[i]，w[i])和一个体积为V的背包，求背包装到的最大价值
状态数组：dp[i][j]为选前i个所用体积为j的最大价值

for(int i=1;i<=n;++i)
      for(int j=1;j<=V;++j)
            dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]);

滚动数组优化：

for(int i=1;i<=n;++i)
      for(int j=V;j>=vi;--j)
            dp[j]=max(dp[j],dp[j-v[i]])+w[i]

完全背包：

问题：n种物品（每种无限个，体积和价值分别为v[i],w[i]）和一个体积为V的背包，求背包最大价值
状态数组：dp[i][j]为选到前i种所用体积为j的最大价值

for(int i=1;i<=n;++i)
      for(int j=0;j<=V;++j)
            for(int k=1;k*v[i]<=j;++k)
                  dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i]);

时间优化

for(int i=1;i<=n;++i)
      for(int j=0;j<=V;++j)
      {
            dp[i][j]=dp[i-1][j];
            if(j>=v[i]) dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i]);
      }

滚动数组空间优化

for(int i=1;i<=n;++i)
      for(int j=V;j>=v[i];--j)
            dp[j]=max(dp[j],dp[j-v[i]]+w[i]);

多重背包

问题：n种物品（每种有限个，数量，体积和价值分别为s[i]，v[i]，w[i]）和一个体积为V的背包，求背包最大价值
状态数组：dp[i][j]为选到前i种所用体积为j的最大价值

for(int i=1;i<=n;++i)
      for(int j=0;j<=V;++j)
            for(int k=0;k*v[i]<=j&&k<=s[i];++k)
                  dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i]);

空间优化

for(int i=1;i<=n;++i)
      for(int j=V;j>=0;--j)
            for(int k=0;k*v[i]<=j&&k<=s[i];++k)
                  dp[j]=max(dp[j],dp[j-k*v[i]]+k*w[i]);

二进制时间优化
将数量为s[i]的物品分成s[i]=1+2+4+8+...+x,然后跑01背包，复杂度由n^3优化为n2logn

代码略

多重背包

问题：既有无限个的，又有单个的，又有多个的，仍然是背包V，求最大价值
单个的可看成多重背包的特殊状况，然后有限个和无限个分别讨论
直接上一维：dp[j]代表用j体积装到的最大价值

for(int i=1;i<=n;++i) cin>>v[i]>>w[i]>>s[i];//当s[i]=0时，为无限个
for(int i=1;i<=n;++i)
      {
            if(s[i]==0)
            {
                  for(int j=V;j>=v[i];--j) dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
            }
            else
            {
                  for(int k=1;k<=s[i];s[i]-=k,k*=2)
                       {
                              for(int k=V;j>=k*v[i];--j)
                                    dp[j]=max(dp[j],dp[j-k*v[i]]+w[i]);
                       }
                  if(!s[i]) continue;
                  for(int j=V;j>=s[i]*v[i];j--)
                        dp[j]=max(dp[j],dp[j-s[i]*v[i]]+s[i]*w[i]);
            }
      }

二维费用的背包问题

问题：n个物品（体积，重量和价值分别为v[i]，m[i]，w[i]）和一个体积为V,限重为M的背包，求背包最大价值
问题：n种物品（每种有限个，数量，体积和价值分别为s[i]，v[i]，w[i]）和一个体积为V的背包，求背包最大价值
加一维就行了
状态数组：dp[i][j]代表体积为i，载重为j时的最大价值

for(int i=1;i<=n;++i)
      for(int j=V;j>=v[i];j--)
            for(int k=M;k>=m[i];--k)
                  dp[j][k]=max(dp[j][k],dp[j-v[i]][k-m[i]]+w[i]);

分组背包

问题：n堆物品，每堆s[i]个，每个体积和价值为v[i],w[i],和一个体积为V背包，每堆物品只能选一个，求最大价值

分组背包看起来没什么用，实际上是各种DP题的热门考点，特别是树形DP
一维状态：dp[j]代表用j体积的最大价值

for(int i=1;i<=n;++i)
      for(int j=V;j>=0;--j)
            for(int k=1;k<=s[i];++k)
                  if(j>=v[k])dp[j]=max(dp[j],dp[j-v[k]]+w[k]);

例题：P2014，2020icpc南京M

有依赖的背包问题

问题：n个物体之间存在着依赖关系，例如依赖关系是一棵树，选择一个节点需要选择其父亲节点

实质上就是一道赤果果的树形DP

状态方程：dp[x][y] 代表x节点选了体积为y的最大价值

void dfs(int s)
{
      for(auto v:edge[s])
      {
            dfs(v);
            for(int j=V;j>=v[s];--j)
                  for(int k=0;k<=j-v[s];++k)
                        dp[s][j]=max(dp[s][j],dp[s][j-k]+dp[v][k]); 
      }
}

第二类问题：n节点数选m点，选一个点必须选父节点，使总价值最大

状态方程：dp[x][i] 代表x节点选择了i个节点的最大价值，答案就是dp[1][m]

void dfs(int s)
{
      for(auto v:edge[s])
      {
            dfs(v);
            for(int i=m;i>=1;--i)
                  for(int j=0;j<i;++j)
                        dp[s][i]=max(dp[s][i],dp[s][i-j]+dp[v][j]);
      }
}

背包问题求方案数

问题：n个物品(体积和价值分别为v[i]，w[i])和一个体积为V的背包，求选取价值达到最大的方案数
只需在原来的基础上加一个计数的数组即可

for(int i=1;i<=n;++i)
      for(int j=V;j>=v[i];--j)
            {
                  if(dp[j-v[i]]+w[i]>dp[j])
                  {
                        dp[j]=dp[j-v[i]]+w[i];
                        num[j]=num[j-v[i]];
                  }
                  else if(dp[j-v[i]]+w[i]==dp[j])
                        num[j]+=num[j-v[i]];
            }

背包问题求出具体方案

问题：n个物品(体积和价值分别为v[i]，w[i])和一个体积为V的背包，求选取价值达到最大的方案

for(int i=1;i<=n;++i)
      for(int j=V;j>=vi;--j)
            dp[j]=max(dp[j],dp[j-v[i]])+w[i]；
int val=V;
for(int i=n;i>=1;--i)
      if(val-v[i]>=0&&dp[val-v[i]]+w[i]==dp[val]) 
            cout<<i<<" ";

如果题目有要求字典序最小，那求解01背包的时候应当倒着求。