背包之专题

标签：背包 15 硬币 int 专题 dp dis

P1282 多米诺骨牌 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

第一题一道思维题

设dis=a[i]−b[i]

f[i][j+dis+N]=min(f[i][j+dis+N],f[i−1][j+N]);//不反转

f[i][j+dis+N]=min(f[i][j+dis+N],f[i−1][j+N]+1);//反转

f[i][j+N]=min(f[i−1][j−dis+N],f[i−1][j+dis+N]+1);

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,mod=998244353;
typedef long long LL;
typedef unsigned long long ULL;
int b[N],c[N],n;
LL dp[N];
int main()
{
    //freopen("perm.in","r",stdin);
    //freopen("perm.out","w",stdout);
    int T;
    cin>>T;
    while(T--)
    {
        memset(dp,0,sizeof(dp));
        int flag=1;
        cin>>n;
        cin>>b[1];
        for(int i=2;i<=n;i++)
        {
            scanf("%d",&b[i]);
            if(b[i]>b[i-1]||b[i]<1||b[i]>n)
                flag=0;
        }
        cin>>c[1];
        for(int i=2;i<=n;i++)
        {
            scanf("%d",&c[i]);
            if(c[i]<c[i-1]||c[i]<1||c[i]>n||c[i]<b[i])
                flag=0;
            if(c[i]>c[i-1]&&b[i]<b[i-1])
                flag=0;
        }
        if(b[1]!=c[1])
            flag=0;
        if(flag==0)
        {
            cout<<0<<endl;
            continue;
        }
        else
        {
            
            int num=1;
            dp[1]=1;
            for(int i=2;i<=n;i++)
            {
                if(b[i]==b[i-1]&&c[i]==c[i-1])
                    dp[i]=dp[i-1]*(c[i]-b[i]+1-num)%mod;
                else if((b[i]==b[i-1]&&c[i]>c[i-1])||(b[i]<b[i-1]&&c[i]==c[i-1]))
                    dp[i]=dp[i-1];
                num++;
            }
            printf("%lld\n",dp[n]);
        }
    }
    return 0;
}

https://www.luogu.com.cn/problem/P2732

一道有意思的题目

一眼望去，背包问题，但是编号和组合的数值都不好存储

看似无从下手，但是再认真观察数据

发现最多只有五种商品，且最多单品购买数不超过五个

由此灵光一现多维dp 多维dp 多维dp

好像可以做

于是设计状态 dp[i][j][k][l][p] 我们令 dp[i][j][k][l][o] 代表当第一种物品有 i 个，第二种物品有 j 个。。。时的最小花费。

于是就得到了一个五维的01背包

代码并不难写

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
struct node{
    int s,k[8],p;
}a[N];
int n,m,f[15][15][15][15][15],b[N],cnt,v[15];
int main()
{
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&a[i].s);
        for(int j=1;j<=a[i].s;j++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            if(b[x]==0) b[x]=++cnt;
            a[i].k[b[x]]=y;
        }
        scanf("%d",&a[i].p);
    }
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        if(b[x]==0) b[x]=++cnt;
        v[b[x]]=y;
        m++;
        a[m].s=1;a[m].k[b[x]]=1;a[m].p=z;
    }
    memset(f,127,sizeof(f));
    f[0][0][0][0][0]=0;
    for(int ki=1;ki<=m;ki++)
     for(int i=a[ki].k[1];i<=v[1];i++)
      for(int j=a[ki].k[2];j<=v[2];j++)
       for(int l=a[ki].k[3];l<=v[3];l++)
        for(int k=a[ki].k[4];k<=v[4];k++)
         for(int r=a[ki].k[5];r<=v[5];r++)
          f[i][j][l][k][r]=min(f[i][j][l][k][r],f[i-a[ki].k[1]][j-a[ki].k[2]][l-a[ki].k[3]][k-a[ki].k[4]][r-a[ki].k[5]]+a[ki].p);
    cout<<f[v[1]][v[2]][v[3]][v[4]][v[5]]<<endl;
    return 0;
}

P2851 [USACO06DEC] The Fewest Coins G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 这题的题意表述比较难以描述，比较奇怪简而言之即交易涉及的硬币要越少越好给你 n 种硬币类型，每种硬币类型 vi 买家有 ci 个，卖家有无限个，买家要买一个 m 元的东西（卖家可以找零），买家问你双方之间交流的硬币个数（指买家用的硬币数 + 卖家找零的硬币数）最少为多少个？

其它题解里面没有详细说明为什么这个题是多重背包+完全背包，这里解释一下。

首先我们来看一下背包都有哪些类型：

01背包：每个物品可以选也可以不选，如果选只能选1个，一般用dp实现；
部分背包：每个物品可以选也可以不选，如果选可以全选或者只选择其中的一部分，用贪心就能实现；
完全背包：每个物品可以选0个，1个，2个，……，无穷多个；
多重背包：每个物品可以选0个，1个，2个，……，n 个（n 一般会在题目中给出），常常用二进制优化拆分为01背包实现。

回到这道题，我们发现，FJ给钱的时候，他可以使用每一种面额的硬币，而且第 i 种硬币可以选择 1,2,3,⋯ ,1,2,3,⋯,ci 个，所以dp FJ给钱的过程用的是多重背包的算法。注意在二进制拆分的时候，不仅钱数要乘以计数器，花费的硬币也要乘以计数器，本人就因为这个问题没有一次AC。如果对二进制拆分不太熟悉，可以看一下宝物筛选那题。

当店主找钱的时候，同样也可以使用所有面额的硬币，但是题目中说店主有无穷多硬币，这不就是完全背包吗？我们枚举店主找的钱，两次dp即可

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+5;
int n,m,v[N],w[N],f[N],dp[N],ans=0x3f3f3f3f,maxx=-10000,sum;
int main()
{
    //freopen("P2851.in","r",stdin);
    //freopen("P2851.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&v[i]);
        maxx=max(maxx,v[i]*v[i]);
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&w[i]); 
        sum=sum+v[i]*w[i];
    }
    if(sum<m)
    {
        cout<<"-1"<<endl;
        return 0;
    }
    memset(f,0x3f,sizeof(f));
    memset(dp,0x3f,sizeof(dp));
    f[0]=dp[0]=0;
    for(int i=1;i<=n;i++)
        for(int j=v[i];j<=maxx;j++)
            f[j]=min(f[j],f[j-v[i]]+1);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=w[i];j<<=1)
        {
            for(int k=m+maxx;k>=j*v[i];k--)
                dp[k]=min(dp[k],dp[k-j*v[i]]+j);
            w[i]-=j;
        }
        if(w[i])for(int j=m+maxx;j>=w[i]*v[i];j--)  dp[j]=min(dp[j],dp[j-w[i]*v[i]]+w[i]);
    }
    for(int i=m;i<=m+maxx;i++)
        ans=min(ans,dp[i]+f[i-m]);
    if(ans==0x3f3f3f3f) cout<<"-1"<<endl;
    else printf("%d\n",ans);
    return 0;
}

P1858 多人背包 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

背包九讲

来分享一下思路.

题解里都说是裸的此类问题,并没有给出解释。

~~(给出的解释也大多是背包九讲里的一些抽象定义~~

本题为01背包的前k优解问题

可以考虑再一维数组再加一维记录当前状态下的前k优解

根据无后效性原则，可以得到成立

很容易发现,我们需要记录用其他物品来填充背包是否能得到更优解.

因此我们需要记录一个变量c1表示体积为j的时候的第c1优解能否被更新.

再去记录一个变量c2表示体积为j-v[i]的时候的第c2优解.

#include<bits/stdc++.h>
using namespace std;
int f[5005][55],ans=0;
int k,v,n,w[205],c[205],t[55];
int main()
{
    memset(f,128,sizeof(f));
    scanf("%d%d%d",&k,&v,&n);
    for (int i=1;i<=n;i++) 
        scanf("%d%d",&w[i],&c[i]);
    f[0][1]=0;
    for (int i=1;i<=n;i++)
        for (int j=v;j>=w[i];j--)
        {
            int t1=1,t2=1,t[60],len=0;
            while (t1+t2<=k+1)
            {
                if (f[j][t1]>f[j-w[i]][t2]+c[i]) 
                    t[++len]=f[j][t1++];
                else   t[++len]=f[j-w[i]][t2++]+c[i];
            }
            for (int K=1;K<=k;K++) f[j][K]=t[K];
        }
    for (int i=1;i<=k;i++) ans+=f[v][i];
    printf("%d",ans);
    return  0;
}

标签：背包,15,硬币,int,专题,dp,dis
From： https://www.cnblogs.com/mingloch/p/17557875.html

相关文章

赞助商

阅读排行