0/1背包问题

• 0/1背包
  • 暴力解决：二维动态规划
  • 改进1：一维动态规划——（优化空间复杂度）
  • 改进2：常数优化

0/1背包

暴力解决：二维动态规划

• 二维dp的定义：$f[i][j]​$: 考虑前i个物品，总体积为j的最大价值为$f[i][j]​$
• 返回结果：$max(f[n][0~v])$,因为背包可以不填满，因此也存在不被选择的物体
• 递推公式：
  • 不选择第i个物品：$f[i][j]=f[i-1][j]$
  • 选择第i个物品：$f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i])​$
• 初始化：$f[0][0]=0​$
• 复杂度：
  • 时间复杂度：$O(nv)​$
  • 空间复杂度：$O(n^2)​$

#include<iostream>
using namespace std;
int N=1001;

int main()
{
    int n,v;
    cin>>n>>v;
    int V[N],W[N];
    for(int i=1;i<=n;i++)
    {
        cin>>V[i]>>W[i];
    }
    int dp[N][N];
    dp[0][0]=0;
    
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=v;j++)
        {
            dp[i][j]=dp[i-1][j];//不选第i个物品
            if(j>=V[i])//选第i个物品
            {
                dp[i][j]=max(dp[i][j],dp[i-1][j-V[i]]+ W[i]);
            }
        }
    }
    //背包可能没填满，但是要遍历完所有的背包
    int res=0;
    for(int i=0;i<=v;i++)res=max(res,dp[n][i]);
    cout<<res;
    return 0;
}

改进1：一维动态规划——（优化空间复杂度）

• 定义dp数组：dp[j],表示容量为j时，最大的价值.

• 递推公式：

  • $dp[j]=max(dp[j-v[i]]+w[i])​$

• 技巧

  • 子程序：1.要保证dp[j]的递推来自第i-1个物品。dp[j]对应第f[i][j]，那么要保证dp[j]的递推来自dp[i-1][j-V[i]]，就要让容量递减的计算，也就是计算dp[v]->dp[0].抽象一个一维数组解决0/1背包的子程序（处理第i个物品）：

    int zeroOnePack(int dp[],int V[],int W[],n,v,i)//i为第i个物品
    {
        for(int j=v;j>=V[i];j--)
        {
            dp[j]=max(dp[j],dp[j-V[i]]+W[i])
        }
    }
    

  • 初始化

    • 要求恰好装满背包：在初始化时除了F [0]为0，其它dp [1..v ]均设为−∞，这样就可以保证最终得到的dp[v ]是一种恰好装满背包的6最优解。
    • 不要求装满背包:dp[0…v]=0

  #include<iostream>
  using namespace std;
  int N=1001;
    
  int main()
  {
      int n,v;
      cin>>n>>v;
      int V[N],W[N],dp[N];
    
      for(int i=1;i<=n;i++)
      {
          cin>>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]);
          }
          //or
          //zeroOnePack(int dp,V,W,n,v,i);
      }
      cout<<dp[v]<<endl;
      return 0;
  }
  

改进2：常数优化

修改下限为low=$max(\sum_i^n W[i],V[i])$

int zeroOnePack(int dp[],int V[],int W[],n,v,i)//i为第i个物品
{
    for(int j=v;j>=low;j--)
        dp[j]=max(dp[j],dp[j-V[i]]+ W[i]);
}