买书题目链接

1023. 买书 - AcWing题库

题目类型

完全背包模板

买书代码

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

using namespace std;

const int N = 1010;

int v[5] = {0, 10, 20, 50, 100};
int f[N];
int main(){
    int m;
    cin>>m;
    f[0]=1;
    for(int i=1; i<=4; i++){
        for(int j=0;j<=m;j++)
        {
            if(j>=v[i])
            {
            	f[j]+=f[j-v[i]];
            }
        }
    }
    cout<<f[m]<<endl;
    return 0;
}

货币系统题目链接

1021. 货币系统 - AcWing题库

题目类型

完全背包模板

货币系统代码

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 3010;

int n,m;
long f[N];
int main(){
    cin>>n>>m;
    f[0]=1;
    int v;
    for(int i=0;i<n;++i)
    {
        cin>>v;
        for(int j=0;j<=m;++j)
        {
            if(j>=v)
                f[j]+=f[j-v];
        }
    }
    printf("%ld\n",f[m]);
    return 0;
}

货币系统题目链接

532. 货币系统 - AcWing题库

题目类型

完全背包模板+数学分析（极大线性无关组）

题目解析

性质1：a1, a2, ..., an 一定都可以被表示出来

性质2：在最优解中，b1, b2, ..., bm可以从a1, a2, ..., an中选出来

性质3：b1, b2, ..., bm一定不能被其他bi表示出来

货币系统代码

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

using namespace std;

const int N = 25010;
int n;
int f[N];
int a[110];
int main()
{
    int T;
    scanf("%d",&T);
    
    while(T--)
    {
        scanf("%d",&n);
        for(int i=0;i<n;++i)
        {
            scanf("%d",&a[i]);
        }
        sort(a,a+n);
        int m = a[n-1];
        int res = 0;
        memset(f,0,sizeof(f));
        f[0]=1;
        for(int i=0;i<n;++i)
        {
            if(!f[a[i]]) res++;
            for(int j=a[i];j<=m;j++){
                f[j]+=f[j-a[i]];
            }
        }
        printf("%d\n",res);
    }
    return 0;
}