货币系统

题目 货币系统

image-52e23949

思路分析

货币使用次数不限 完全背包

它这个不同种类的货币面值可能相同让我怀疑是多重背包 （把所有物品记录一下 一样的在s[i]里累加数量） 但与前面使用次数不限矛盾 所以他这个情况其实完全可以忽略了 都包含在上一类价值一样的选法里去了

还是画个图 v种货币 n=v N元钱 m=N 属性count 差不多了

image-7c474cba

代码实现

#include<bits/stdc++.h>

using namespace std;

const int N=10010;

long long dp[N];

int n,m;

int main()

{

    cin>>n>>m;

    dp[0]=1;

    for(int i=1;i<=n;i++){

        int v; cin>>v;

        for(int j=v;j<=m;j++)

            dp[j]=dp[j]+dp[j-v];

    }

    cout<<dp[m];

    return 0;

}

同类题型

视频讲解

⬅️ 自然数拆分 🏠 00-刷题理模型 ➡️ 完全背包问题