---
title: "货币系统"
created: 2025-11-28
tags:
  - 算法
---

# 货币系统

## 题目 [货币系统](https://www.acwing.com/problem/content/description/1373/)

![[image-52e23949.png]]

## 思路分析

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

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

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

![[image-7c474cba.png]]

## 代码实现

```cpp
#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-刷题理模型]] ➡️ [[完全背包问题|完全背包问题]]