洛谷P1450 [HAOI2008]硬币购物(有个数限制的多重背包 完全背包+容斥/完全背包+回滚背包)

题目

共有 4 种硬币，面值分别为 c1​,c2​,c3​,c4​。

某人去商店买东西，去了 n 次。

对于每次购买，他带了 di​ 枚 i 种硬币，想购买 s 的价值的东西。

请问每次有多少种付款方法。

数据范围：1<=ci,di,s<=1e5，n<=1000

思路来源

洛谷题解

题解1（完全背包+容斥）

有个数限制的背包=没有个数限制的背包+容斥超限部分

只有4种数，可以枚举哪些是超过数量上限的

先用不限制次数的做完全背包，然后枚举超过数量上限的集合做容斥

容斥某个集合时，先将一定会引起超限的量取出来，

这样剩下的任意取也会超限，统计与其对应的超限的方案

复杂度：

题解2（完全背包+回滚背包）

有个数限制的背包=没有个数限制的背包+撤销超限的转移

没有个数限制的背包即完全背包，先做完全背包

有了di的限制之后，考虑把来自>di的转移给撤销掉，回答完询问之后再加回来

完全背包本质上是对若干个位置做了dp的前缀和，而有个数限制时，相当于前缀和作差

复杂度：

量级上比较极限，但是因为背包转移常数较小，所以可以通过

代码1

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int c[4],d[4],s,n;
ll dp[N];
int main(){
    dp[0]=1;
    for(int i=0;i<4;++i){
        scanf("%d",&c[i]);
        for(int j=c[i];j<N;j++){
            dp[j]+=dp[j-c[i]];
        }
    }
    scanf("%d",&n);
    while(n--){
        for(int i=0;i<4;++i){
            scanf("%d",&d[i]);
        }
        scanf("%d",&s);
        int up=1<<4;
        ll ans=0;
        for(int i=0;i<up;++i){
            int cnt=0,now=s;
            for(int j=0;j<4;++j){
                if(i>>j&1){
                    cnt++;
                    now-=c[j]*(d[j]+1);
                }
            }
            if(now<0)continue;
            if(cnt&1)ans-=dp[now];
            else ans+=dp[now];
        }
        printf("%lld\n",ans);
    }
    return 0;
}

代码2

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int c[4],d[4],s,n;
ll dp[N];
int main(){
    dp[0]=1;
    for(int i=0;i<4;++i){
        scanf("%d",&c[i]);
        for(int j=c[i];j<N;j++){
            dp[j]+=dp[j-c[i]];
        }
    }
    scanf("%d",&n);
    while(n--){
        for(int i=0;i<4;++i){
            scanf("%d",&d[i]);
            int w=c[i]*(d[i]+1);
            for(int j=N-1;j>=w;--j){
                dp[j]-=dp[j-w];
            }
        }
        scanf("%d",&s);
        printf("%lld\n",dp[s]);
        for(int i=0;i<4;++i){
            int w=c[i]*(d[i]+1);
            for(int j=w;j<N;++j){
                dp[j]+=dp[j-w];
            }
        }
    }
    return 0;
}