背包问题(模板)

简介: 背包问题(模板)

01背包


从最大容量开始遍历到当前,防止重复

void solve()
{
  int n,m,v,w;
  cin>>n>>m;
  for(int i=1;i<=n;i++)
  {
    cin>>v>>w;
    for(int j=m;j>=v;j--)
    {
      dp[j]=max(dp[j],dp[j-v]+w);
    }
  }
  cout<<dp[m]<<endl;
  return ;
}


完全背包


从当前容量遍历到最大,与01背包恰好相反

void solve()
{
  int n,m,v,w;
  cin>>n>>m;
  for(int i=1;i<=n;i++)
  {
    cin>>v>>w;
    for(int j=v;j<=m;j++)
    {
      dp[j]=max(dp[j],dp[j-v]+w);
    }
  }
  cout<<dp[m]<<endl;
  return ;
}


多重背包(范围0-100):


范围小的时候适用,将有数量都转为1,转化为01背包

void solve()
{
  int n,m,v[101001],w[101001],ans=1,a,b,c;
  cin>>n>>m;
  for(int i=1;i<=n;i++)
  {
    cin>>a>>b>>c;
    for(int j=1;j<=c;j++)
    {
      v[ans]=a;
      w[ans]=b;
      ans++;
    }
  }
  for(int i=1;i<=ans;i++)
  {
    for(int j=m;j>=v[i];j--)
    {
      dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
    }
  }
  cout<<dp[m]<<endl;
  return ;
}


混合背包:


void solve()
{
  int n,m;
  cin>>n>>m;
    for (int i=1;i<=n;i++) 
    {
        int v,w,s;
        cin>>v>>w>>s;
        if(s==0)//当完全背包做
        {
            for(int j=v;j<=m;j++) 
            dp[j] = max(dp[j],dp[j-v]+w);
        }
        else //转化为01背包
        {
            if(s==-1)
            s=1;
            for(int k=1;k<=s;k<<=1)
            {
              for(int j=m;j>=v*k;j--)
              {
                dp[j]=max(dp[j],dp[j-v*k]+w*k);
        }
        s-=k;
      }
      if(s)
      {
        for(int j=m;j>=s*v;j--)
        {
           dp[j]=max(dp[j],dp[j-v*s]+w*s);  
        }
      }
        }
    }
    cout<<dp[m]<<endl; 
  return ;
}


分组背包:


signed main()
{
  int n,m,s,w[1010],v[1010];
  cin>>n>>m;
  while(n--)
  {
  cin>>s;
  for(int i=1;i<=s;i++)
  cin>>v[i]>>w[i];
  for(int j=m;j>=0;j--)
  {
    for(int k=1;k<=s;k++)
    {
    if(j>=v[k])
    dp[j]=max(dp[j],dp[j-v[k]]+w[k]);
    }
  }
  }
  cout<<dp[m]<<endl;
  return 0;
}


二维费用的背包问题:


除体积限制外多了质量限制

void solve()
{
  int n,v,m;
  cin>>n>>v>>m;
    for (int i=1;i<=n;i++) 
    {
        int a,b,w;
        cin>>a>>b>>w;
        for(int j=v;j>=a;j--)
        {
          for(int k=m;k>=b;k--)
          {
            dp[j][k]=max(dp[j][k],dp[j-a][k-b]+w);
      }
    }
    }
    cout<<dp[v][m]<<endl; 
  return ;
}


背包问题求方案数:


signed main()
{
  int n,m,v,w;
  cin>>n>>m;
  for(int i=0;i<=m;i++)
  cnt[i]=1;
  for(int i=1;i<=n;i++)
  {
    cin>>v>>w;
    for(int j=m;j>=v;j--)
    {
      int t=dp[j-v]+w;
      if(t>dp[j])
      {
        dp[j]=t;
        cnt[j]=cnt[j-v];
      }
      else if(t==dp[j])
      {
        cnt[j]=(cnt[j]+cnt[j-v])%mod;
      }
    }
  }
  cout<<cnt[m]<<endl;
  return 0;
}

目录
相关文章
|
7月前
树状数组模板
树状数组模板
43 0
最小生成树(模板)
最小生成树(模板)
37 0
|
5月前
|
算法
二分 模板
二分的另一个板子
40 1
|
7月前
|
Python
{二分模板}
{二分模板}
28 0
|
7月前
二分图相关模板
二分图相关模板
34 0
|
SQL 人工智能 开发框架
线段树模板+例题
线段树模板+例题
81 1
|
算法
树状数组模板与练习
树状数组模板与练习
102 0
二分搜索的三种模板
二分搜索的三种模板
69 0
|
项目管理
求组合数(模板)【组合数学】
求组合数(模板)【组合数学】
152 0
求组合数(模板)【组合数学】
|
人工智能 BI C语言
【数论】【模板】
【数论】【模板】
103 0