头像

ZPOP




离线:4小时前


最近来访(13)
用户头像
lumoumou
用户头像
Erase_easy
用户头像
派大星_1
用户头像
小雪菜本大菜
用户头像
hakusai
用户头像
一只小锦李
用户头像
yxc
用户头像
长小圆

活动打卡代码 AcWing 1021. 货币系统

ZPOP
18小时前

完全背包求方案数

注意:这里的答案是阶乘级别,需要用long long存储

代码:

#include <iostream>
using namespace std;
const int N=3010;
long long  f[N];
int n,m;
int main()
{
        cin>>n>>m;
        f[0]=1;
        for(int i=1;i<=n;i++)
        {
                int a;
                cin>>a;
                for(int j=a;j<=m;j++)
                        f[j]+=f[j-a];
        }
        cout<<f[m]<<endl;
        return 0;
}


活动打卡代码 AcWing 1019. 庆功会

ZPOP
19小时前

朴素版的多重背包问题能过

代码:

#include <iostream>
#include <algorithm>
using namespace std;
const int M=6060;
int f[M];
int n,m;
int main()
{
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
                int v,w,s;
                cin>>v>>w>>s;
                for(int j=m;j>=0;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]<<endl;
        return 0;
}


活动打卡代码 AcWing 278. 数字组合

ZPOP
1天前

01背包问题求方案数的应用

DP:
1.状态表示:f[i][j]表示从前i个物品中选,且体积恰好为j的方案的总数

2.状态计算:

1. 当不选第i个物品时,f[i][j]=f[i-1][j];

2. 当选择第i个物品时,f[i][j]+=f[i][j-v]

初始化时,只有f[0][0]是合法方案(空集,算一种方案,就是什么都不选且也不需要选),其余的f[0][1]~f[0][m]都不合法,为了让他不参与运算,赋值为0


代码:

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

        return 0;
}


活动打卡代码 AcWing 1020. 潜水员

ZPOP
1天前

这一题主要是要掌握这三种状态的表示:

1. f[i][j]所在集合:表示从前i个物品中选,体积最多j的方案数
    初始值全为0,并且要保证j-v>=0

2. f[i][j]所在集合:表示从前i个物品中选,体积恰好j的方案数
    初始值只有f[0][0]为0,并且为了识别非法状态,将其赋值为一个不参与运算的数,并且要保证j-v>=0

3. f[i][j]所在集合:表示从前i个物品中选,体积至少j的方案数
    初始值只有f[0][0]为0,并且为了识别非法状态,将其赋值为一个不参与运算的数,此时j-v可以为负数

DP:
1. 状态表示:f[i][j][k]表示从前i个物品中选,并且费用1总数至少为j、费用2总数至少为k的最小值

2. 状态计算:和二维的01背包一样

但是虽然这一题f[i][-x][-y]合法,但是由于数据都>=1,这些的最小值都为f[i][0][0]


代码:

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=30,M=90;
int f[N][M];
int n,m,k;
int main()
{
        cin>>n>>m>>k;
        memset(f,0x3f,sizeof f);//为了确保不用非法值
        f[0][0]=0;
        for(int i=1;i<=k;i++)
        {
                int a,b,c;
                cin>>a>>b>>c;
                for(int j=n;j>=0;j--)
                        for(int x=m;x>=0;x--)
                                f[j][x]=min(f[j][x],f[max(j-a,0)][max(x-b,0)]+c);
        }
        cout<<f[n][m]<<endl;
        return 0;
}



ZPOP
2天前

二维费用的背包问题可以与所有背包问题相结合

这一题是与01背包相结合
它的状态表示、状态计算以及优化与01背包几乎一样,就是维度升了一维

代码:

#include <bits/stdc++.h>
using namespace std;
const int V=110,M=110;
int f[V][M];
int n,v,m;
int main()
{
        cin>>n>>v>>m;
        for(int i=1;i<=n;i++)
        {
                int sv,sm,w;
                cin>>sv>>sm>>w;
                for(int j=v;j>=sv;j--)
                        for(int k=m;k>=sm;k--)
                                f[j][k]=max(f[j][k],f[j-sv][k-sm]+w);
        }
        cout<<f[v][m]<<endl;
        return 0;
}



ZPOP
4天前

男人八题之一

对于完全背包的优化,我们发现他是求所有前缀中的最大值,所以用一个变量来更迭,只是这个变量恰好是f[i,j-v]+w

而对于多重背包的优化,我们要求的是中间一段的最大值,就算我们知道某几个确定元素和整体的最大值
由于存在不等关系,也无法知道区间内的最大值,所以无法使用完全背包问题的优化方式

但是通过对比f[i,j],f[i,j-v],f[i,j-2v],f[i,j-3v]...,f[i,j-kv]

我们可以发现j,j-v,j-2v,...,j-kv都有一个特点,就是模v的余数r相同(也就是j一直减v,最后不够减去v的体积)
这样就用r把j,j-v,j-2v,…,j-kv这些数从后面最小的j-kv转化为到了[r,r+v,r+2v,...,j-v,j]
求f[i,j]就是求[r,r+v,r+2v,…,j-v,j]中包含j-v往前的s个数的最大值,取不到s个就特判成有几个取几个,f[i,j-kv]也是以此类推

这种数据结构就对应了基础课的单调队列
所以多重背包的优化就是求长度固定为s的滑动窗口中的最大值,但因为每个f[i,j-kv]之间存在一个偏移量,所以还要加上一个关于w的偏移量


代码:

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N=20010;
int f[N];
int g[N];//用滚动数组存储上一层的f[i];
int q[N];//队列
int n,m;
int main()
{
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
                int v,w,s;
                cin>>v>>w>>s;

                memcpy(g,f,sizeof f);//先把枚举前的那一层状态存下来

                for(int r=0;r<v;r++)//枚举余数,最小是0(表示m%v==0),最大<v(表示kv->m,但是小于m)
                {
                        int hh=0,tt=-1;//定义单调队列的头和尾

                        for(int k=r;k<=m;k+=v)//枚举坐标轴上的值,从余数r开始,到放不下结束
                        {
                                if(hh<=tt && q[hh]<k-s*v)   hh++;
                    //下标都是v的整数倍,如果k-s*v>q[hh],说明q[hh]这个数已经在窗口外面,hh++让它出队
                                if(hh<=tt) f[k]=max(f[k],g[q[hh]]+(k-q[hh])/v*w);//求的是窗口内部最大值
                    //q[hh]就是最大值的下表,所以g[q[hh]]就是f[]的最大值,后面还要加上窗口内元素个数*w,

                                while(hh<=tt&& g[q[tt]]-(q[tt]-r)/v*w <= g[k]-(k-r)/v*w)        tt--;
                                //单调队列弹出不合法元素(要求队列递减)
                                q[++tt]=k;
                        }
                }
        }
        cout<<f[m]<<endl;
        return 0;
}



ZPOP
4天前

二维费用的01背包问题

费用V1:精灵球的数量
费用V2:皮卡丘的体力

价值:精灵本身

状态表示和计算与01背包问题一样

同样这一题可以把第一维优化掉

  1. 第一问要求的结果:f[V1]V2-1
  2. 而第二问就是在f[V1][0]~f[V1][V2-1]找第二维费用最低的,且等于f[V1][V2-1]的消耗最小体力t,再用V2-t(因为我们求的是消耗最低体力,而题目要求的是剩余最大体力)

代码:

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=1010,M=510,K=110;
int f[N][M];
int V1,V2,n;
int main()
{
        cin>>V1>>V2>>n;
        for(int i=1;i<=n;i++)
        {
                int v1,v2;
                cin>>v1>>v2;
                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 t=1e9;
        for(int j=0;j<=V2-1;j++)
                if(f[V1][V2-1]==f[V1][j])
                        t=min(t,j);
        cout<<V2-t<<endl;
        return 0;
}


活动打卡代码 AcWing 1023. 买书

ZPOP
5天前

完全背包求方案数

代码:

#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int f[N];
int w[5]={0,10,20,50,100};
int n;
int main()
{
        cin>>n;
        f[0]=1;//一本书都不买也是一种方案
        for(int i=1;i<=4;i++)
        {
                for(int j=w[i];j<=n;j++)
                        f[j]+=f[j-w[i]];
        }
        cout<<f[n]<<endl;
        return 0;
}


活动打卡代码 AcWing 1024. 装箱问题

ZPOP
5天前

和普通的01背包没什么区别,就是w[]和v[]是同一个

代码1:朴素版

#include <iostream>
#include <algorithm>
using namespace std;
const int N=40,M=20020;
int f[N][M];
int v[N];
int n,m;
int main()
{
        cin>>m>>n;
        for(int i=1;i<=n;i++)
                cin>>v[i];

        for(int i=1;i<=n;i++)
                for(int j=0;j<=m;j++)
                {
                        f[i][j]=f[i-1][j];
                        if(j>=v[i])
                                f[i][j]=max(f[i][j],f[i-1][j-v[i]]+v[i]);
                }
        cout<<m-f[n][m]<<endl;
        return 0;
}

代码2:优化版

#include <iostream>
#include <algorithm>
using namespace std;
const int N=40,M=20020;
int f[M];
int v[N];
int n,m;
int main()
{
        cin>>m>>n;
        for(int i=1;i<=n;i++)
                cin>>v[i];

        for(int i=1;i<=n;i++)
                for(int j=m;j>=v[i];j--)
                        f[j]=max(f[j],f[j-v[i]]+v[i]);
        cout<<m-f[m]<<endl;
        return 0;
}


活动打卡代码 AcWing 423. 采药

ZPOP
5天前

01背包问题加了一个背景

代码:

#include <iostream>
#include <algorithm>
using namespace std;
const int N=110,M=1010;
int f[M];
int w[N],t[N];
int n,m;
int main()
{
        cin>>n>>m;

        for(int i=1;i<=m;i++)
                cin>>t[i]>>w[i];

        for(int i=1;i<=m;i++)
                for(int j=n;j>=t[i];j--)
                        f[j]=max(f[j],f[j-t[i]]+w[i]);
        cout<<f[n]<<endl;
        return 0;
}