3 背包问题及其衍生

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int f[N];//滚动数组优化后的
int main()
{
    int n,m;
    cin>>m>>n;
    for(int i=0;i<n;i++)
    {
        int v,w;
        cin>>v>>w;
        for(int j=m;j>=v;j--) f[j]=max(f[j],f[j-v]+w);//从打到小滚动，要么选当前数，要么不选
    }
    cout<<f[m]<<endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=2e4+10;
int f[N];
int main()
{
    int n,m;
    cin>>m>>n;
    for(int i=0;i<n;i++)
    {
        int v;
        cin>>v;
        for(int j=m;j>=v;j--) f[j]=max(f[j],f[j-v]+v);
    }
    cout<<m-f[m]<<endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=3e4+10;
int f[N];
int main()
{
   int n,m;
   cin>>m>>n;
   for(int i=1;i<=n;i++)
   {
       int v,w;
       cin>>v>>w;
       for(int j=m;j>=v;j--)
         f[j]=max(f[j],f[j-v]+v*w);
   }
   cout<<f[m];
   return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int f[N][N];
int main()
{
   int n,b,c;
   scanf("%d%d%d",&n,&b,&c);
   for(int i=1;i<=n;i++) {
       int v,m,w;
       scanf("%d%d%d",&v,&m,&w);
    for(int j=b;j>=v;j--)//优化一维
      for(int k=c;k>=m;k--)
       f[j][k]=max(f[j][k],f[j-v][k-m]+w);//要么选第i个，要么不选第i个
   }
   printf("%d",f[b][c]);
   return 0;
}

1. ##include<bits/stdc++.h>
using namespace std;
const int K=1e3+10,M=510;
int f[K][M];//滚动数组优化
int main()
{
    int V1,V2,n;
    cin>>V1>>V2>>n;
    for(int i=1;i<=n;i++)
    {
        int v1,v2;
       cin>>v1>>v2;
       //滚动数组从大到小滚，这样就会用到i-1的值了，不会用到第i层的值
       for(int j=V1;j>=v1;j--)//状态计算
           for(int k=V2-1;k>=v2;k--)
                  f[j][k]=max(f[j][k],f[j-v1][k-v2]+1);//更新最大值，要么选这个精灵，要么不选
    }
    cout<<f[V1][V2-1]<<' ';//输出最大可以收服的数量
    int k=V2-1;
    while(k>0&&f[V1][k-1]==f[V1][V2-1]) k--;//假如在V1的条件下，求最大的不相等的值
    cout<<V2-k<<endl;//输出剩余的体力
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=22,M=80;
int f[N][M];
int main()
{
  int V1,V2,n;
  cin>>V1>>V2>>n;
  memset(f,0x3f,sizeof f);
  f[0][0]=0;//表示前0个物品选第一个体积V1至少为0的,第二个体积V2至少为0的价值为0，而其他不存在初始化为正无穷，表示更新最小值不用到他
  for(int i=1;i<=n;i++)
  {
      int v1,v2,w;
      cin>>v1>>v2>>w;
      for(int j=V1;j>=0;j--)
        for(int k=V2;k>=0;k--)
           f[j][k]=min(f[j][k],f[max(0,j-v1)][max(0,k-v2)]+w);//假如小于0，就让他等于0
  }
  cout<<f[V1][V2]<<endl;//输出至少为V1和V2的最小价值
   return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int f[N];
int main()
{
   int n,m;
   cin>>n>>m;
   //多重背包1
   for(int i=1;i<=n;i++)
   {
      int v,w,s;
      cin>>v>>w>>s;
      for(int j=m;j>=v;j--)
        for(int k=0;k<=s&&k*v<=j;k++)
           f[j]=max(f[j],f[j-k*v]+k*w);
   }
   cout<<f[m];
   return 0;
}

1. #in#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int f[N],v[4]={10,20,50,100};//把书的费用看成体积
int main()
{
  int n;
  cin>>n;
  f[0]=1;//前0本书，价格为0的有一种方案，其他不合法，方案数为0，因为没有书得不到其他价格
  for(int i=0;i<4;i++)
  {
      for(int j=v[i];j<=n;j++)
        f[j]+=f[j-v[i]];
  }
  cout<<f[n]<<endl;
   return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> pii;
const int N=32010;
pii zhu[N];//用来存主件
vector<pii> fu[N];//用来附件主件
int f[N];
int main()
{
   int n,m;
   cin>>m>>n;
   for(int i=1;i<=n;i++)
   {
       int v,w,q;
       cin>>v>>w>>q;
       if(!q) zhu[i]={v,v*w};//把主件放进去
       else fu[q].push_back({v,v*w});//把附件存该主件下的附件
   }
   for(int i=1;i<=n;i++)
     if(zhu[i].x)//假如是主件
       for(int j=m;j>=0;j--)
        {
            int g=fu[i].size();//表示该主件附件的数
            for(int k=0;k<1<<g;k++)//二进制枚举在附件有g个的情况下的选法
           {
               int v=zhu[i].x,w=zhu[i].y;
               for(int u=0;u<g;u++)//枚举位数，判断该位数是否为1，为1则选该附件
                 if(k>>u&1) v+=fu[i][u].x,w+=fu[i][u].y;
               if(j>=v) f[j]=max(f[j],f[j-v]+w);//假如合法，则转移
           }
        }
   cout<<f[m];
   return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int f[N];
int main()
{
   int n,m;
   cin>>n>>m;
   f[0]=1;//表示前0个物品选恰好等于0的方案数为1，而其他从前0个选恰好为1，2，3的这种情况不可能有，所以其他是0
   for(int i=0;i<n;i++)
   {
       int v;
       cin>>v;
       for(int j=m;j>=v;j--)
          f[j]+=f[j-v];
   }
   cout<<f[m];
   return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
long long f[N];
int main()
{
    int n,m;
    cin>>n>>m;
    f[0]=1;//因为前0个物品恰好为0的也是一种情况
    for(int i=1;i<=n;i++)//完全背包
    {
        int v;
        cin>>v;
        for(int j=v;j<=m;j++)
            f[j]+=f[j-v];//求方案数
    }
    cout<<f[m];
   return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=25010,M=110;
int f[N],a[M];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,cnt=0;
        cin>>n;
        for(int i=0;i<n;i++) cin>>a[i];
        sort(a,a+n);//将a从小到大排序
        memset(f,0,sizeof f);//把上一次的状态清空
        f[0]=1;//前0个数能表示0也是一种方案
        int m=a[n-1];//最大要表示的数，也即最大体积
        for(int i=0;i<n;i++)//多重背包求方案数
        {
            int v=a[i];//v是当前数
            if(!f[v]) cnt++;//假如这个数不能被表示，也即方案数为0的时候，说明这个数必不可缺
            for(int j=v;j<=m;j++) f[j]+=f[j-v];//求表示每个数的方案数
        }
        cout<<cnt<<endl;
    }
   return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1010,mod=1e9+7;
int f[N],g[N];//f的状态转移方程为体积恰好为j的最大价值
int main()
{
    int n,m;
    cin>>n>>m;
    memset(f,-0x3f,sizeof f);//由于是恰好为j，则初始化为正无穷
    f[0]=0;//前0个体积恰好为0的最大价值为0
    g[0]=1;//前0个体积恰好为0有一个方案数
    for(int i=0;i<n;i++)
    {
       int v,w;
       cin>>v>>w;
       for(int j=m;j>=v;j--)
       {
           int maxv=max(f[j],f[j-v]+w),cnt=0;//用maxv记录哪边的最大值，cnt记录该体积下的方案数
           if(maxv==f[j]) cnt+=g[j];//假如最大价值是f[i-1][j],则方案数加上g[i-1][j]
           if(maxv==f[j-v]+w) cnt+=g[j-v];//假如最大价值是f[i-1][j-v],则方案数加上g[i-1][j-v]
           g[j]=cnt%mod;//该体积下的最大价值的方案数
           f[j]=maxv;//更新最大价值
       }
    }
    //由于是恰好体积为j，所以不知道最大价值对应的体积是哪个
    int res=0;
    for(int i=0;i<=m;i++) res=max(res,f[i]);
    //求一下最大价值对应的方案数
    int ans=0;
    for(int i=0;i<=m;i++)
        if(res==f[i])
          ans=(ans+g[i])%mod;
    cout<<ans<<endl;
   return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int f[N][N],v[N],w[N];
int main()
{
  int n,V;
  cin>>n>>V;
  for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
  //从后往前更新选的数
  for(int i=n;i;i--)
      for(int j=0;j<=V;j++)
      {
          f[i][j]=f[i+1][j];//这步不能少，表示不选第i个数的时候，待会输出方案时要用到
          if(j>=v[i]) f[i][j]=max(f[i][j],f[i+1][j-v[i]]+w[i]);
      }
      //从前往后输出选的数，也就是选最大时的方案
  for(int i=1,j=V;i<=n;i++)
   if(j>=v[i]&&f[i][j]==f[i+1][j-v[i]]+w[i]) cout<<i<<' ',j-=v[i];
   return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int f[N];
int main()
{
    int n,V;
    cin>>n>>V;
    for(int i=0;i<n;i++)
    {
        int v,w,s;
        cin>>v>>w>>s;
        if(s==0)//完全背包求最大价值
           for(int j=v;j<=V;j++) 
             f[j]=max(f[j],f[j-v]+w);
        else//多重背包用二进制优化成01背包做法
        {
            if(s==-1) s=1;//假如是01背包，则s的数量为1
            for(int k=1;k<=s;s-=k,k*=2)//二进制优化多重背包
                for(int j=V;j>=k*v;j--)//枚举每个数量下的最大价值
                    f[j]=max(f[j],f[j-k*v]+k*w);
            if(s)//假如还有剩余，则在求一次最大值
                for(int j=V;j>=s*v;j--) f[j]=max(f[j],f[j-s*v]+s*w);
        }
    }
    cout<<f[V]<<endl;
   return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int v[N],w[N];
int h[N],e[N],ne[N],idx;//领接表来存树
int f[N][N];
int n,m;
void add(int a,int b)//把a连到b的后面
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u)
{
    for(int i=h[u];i!=-1;i=ne[i])//枚举物品组，也就是子根
    {
        int son=e[i];
        dfs(son);//先求子根的最大值才用来更新自己的
        //分组背包求最大价值
        for(int j=m-v[u];j>=0;j--)//循环体积，因为自己占v[u]的体积，则求的时候得小于等于m-v[u]
            for(int k=0;k<=j;k++)//循环决策，子根的体积就是决策，按体积划分
               f[u][j]=max(f[u][j],f[u][j-k]+f[son][k]);
    }
    //把物品u的体积下的价值存进去，用来更新他的父节点
    for(int i=m;i>=v[u];i--) f[u][i]=f[u][i-v[u]]+w[u];
    for(int i=0;i<v[u];i++) f[u][i]=0;//假如体积加上父节点的体积大于最大容量了，则价值不存在，也就是为0
}
int main()
{
   cin>>n>>m;
   memset(h,-1,sizeof h);//初始化头结点为-1
   int root;
   for(int i=0;i<n;i++)
   {
       int v,w,p;
       cin>>v>>w>>p;
       if(p==-1) root=i;
       else add(p,i);
   }
   dfs(root);
   cout<<f[root][m]<<endl;//输出以这个为根的最大价值
   return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int n;
struct Stone//定义一个结构体来存能量石的三个数
{
    int s,e,l;
    bool operator<(const Stone &W) const//重载小于号，也就是按照推出来的公式进行排序
    {
        return s*W.l<l*W.s;
    }
}stone[N];
int f[N];
int main()
{
   int t;
   cin>>t;
   for(int C=1;C<=t;C++)
   {
       int m=0;//用来存能量石总能量
       cin>>n;
       for(int i=0;i<n;i++)
       {
           int s,e,l;
           cin>>s>>e>>l;
           stone[i]={s,e,l};
           m+=s;
       }
       sort(stone,stone+n);//按照贪心的排序
       memset(f,0,sizeof f);//清空上一状态
       for(int i=0;i<n;i++)
       {
           int s=stone[i].s,e=stone[i].e,l=stone[i].l;
           for(int j=m;j>=s;j--)//01背包求最大值
            f[j]=max(f[j],f[j-s]+e-(j-s)*l);
       }
       int ans=0;
       for(int i=0;i<=m;i++) ans=max(ans,f[i]);//求一次最大能量值
       printf("Case #%d: %d\n",C,ans);
   }
   return 0;
}