3 背包问题及其衍生

目录

1 多重背包3（单调队列优化）

2 采药（裸01背包）

3 装箱问题 (裸01背包)

4 宠物小精灵之收服 (二维背包费用问题)

1 多重背包3（单调队列优化）

6. 多重背包问题 III - AcWing题库

(5条消息) 17 堆排序与模拟堆_钊气蓬勃.的博客-CSDN博客

 

#include
using namespace std;
const int N=2e4+10;
int f[N],q[N],g[N];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i 
 
2 采药（裸01背包） 
 
423. 采药 - AcWing题库
 
#include
using namespace std;
const int N=1e3+10;
int f[N];//滚动数组优化后的
int main()
{
    int n,m;
    cin>>m>>n;
    for(int i=0;i>v>>w;
        for(int j=m;j>=v;j--) f[j]=max(f[j],f[j-v]+w);//从打到小滚动，要么选当前数，要么不选
    }
    cout< 
 
3 装箱问题 (裸01背包) 
 
只不过问剩余体积，那就v也看出w来做，最后V-价值最大就行了
 
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
 
#include
using namespace std;
const int N=2e4+10;
int f[N];
int main()
{
    int n,m;
    cin>>m>>n;
    for(int i=0;i>v;
        for(int j=m;j>=v;j--) f[j]=max(f[j],f[j-v]+v);
    }
    cout< 
 
4 二维费用的背包问题 
 
8. 二维费用的背包问题 - AcWing题库
 
 
#include
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;
}
 
 
 
5 宠物小精灵之收服 (二维背包费用问题) 
 
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
 
 
 
#include
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<0&&f[V1][k-1]==f[V1][V2-1]) k--;//假如在V1的条件下，求最大的不相等的值
    cout< 
6 潜水员（二维背包）
 
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
 
 
7   数字组合（01背包求方案数）
 
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
 
 
 
 
#include
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>v;
       for(int j=m;j>=v;j--)
          f[j]+=f[j-v];
   }
   cout< 
8 庆功会 （裸多重背包）
 
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
 
#include
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< 
9 买书（裸完全背包）
 
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
 
 
 
 
 
 
#include
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<