题意

$n$ 种纸币，面额为 $a_i$（如：10RMB、50RMB、100RMB），求 $w$ 元钱最少要多少张纸币凑出来（如：11RMB 用 1 张 10 元和 1 张 1 元）

思路

每种钱币都算出每元钱要用的纸币数，然后和现在的钱数对比

代码

#include <bits/stdc++.h>
using namespace std;
int a[10005],w[1005];
int main(int argc, char **argv){
	memset(a,0x7f,sizeof(a));	// 最大化数组
	int n,m;
	cin >> n >> m;
	for (int i = 1;i <= n;i++){	// 输入钱币的面额
		cin >> w[i];
	}
	a[0] = 0;	// 0 元用 0 张钱币（边界）
	for (int j = 1;j <= n;j++){
		for (int i = w[j];i <= m;i++){	// 从钱币的面额开始比，不然会 RE
			a[i] = min(a[i - w[j]] + 1,a[i]);	// 前几张和目前比大小
		}
	}
	cout << a[m];
	return 0;
}

题意

与这道题大致相同,只是不是用1,5,11,点我查看

思路

点我查看

代码

#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
int a[114514];
int qb[114514];//钱币(Q币)
int fmin(int x,int y)//计算最小值
{
	int mi=114514;
	for(int i=0;i<y;i++)
	{
		mi=min(mi,a[x-qb[i]]);
	}
	return mi;
}
int main()
{
	cin>>m>>n;//输入
	for(int i=0;i<m;i++)
	{
		cin>>qb[i];//输入
	}
	for(int i=1;i<=n;i++)
	{
		bool f=0;
		for(int j=0;j<m;j++)//每一个钱币
		{
			if(i<qb[j])
			{
				a[i]=fmin(i,j)+1;//取最小值
				f=1;//标记
				break;//要退出
			}
		}
		if(!f)
		{
			a[i]=fmin(i,m)+1;//否则
		}
	}
	cout<<a[n];//输出
	return 0;
}

BFS

#include<bits/stdc++.h>
using namespace std;
struct s{
    int a,b;//a是当前钱数，b是用了几个阴币
};
int n,m,vis[int(1e4+10)];//防止MLE && TLE
int arr[int(1e3+5)];
queue<s> q;
int main(){
    cin>>m>>n;
    for(int i=0;i<m;i++) cin>>arr[i];
    q.push({0,0});
    while(q.size()){
        int a=q.front().a,b=q.front().b;
        q.pop();
        if(a==n){
            cout<<b;
            return 0;
        }
        vis[a]=1;
        for(int i=0;i<m;i++){
            if(a+arr[i]<=n && !vis[a+arr[i]]){
                vis[a+arr[i]]=1;
                q.push({a+arr[i],b+1});
            }
        }

    }
    return 0;
}

DP

#include<iostream>
#include<algorithm>
using namespace std;
int a[int(1e6)];
int money[1001];
int main()
{
	int n,w;
	cin >> n >> w;
	for (int i=0;i<n;i++){
		cin >> money[i];
	}
	a[1]=1;
	for (int i=2;i<=w;i++)
	{
		int j=0,minn=9999999;
		while(money[j]<=i && j<n){
			minn=min(minn,a[i-money[j]]);
			j++;
		}
		a[i]=minn+1;
	}
	cout << a[w];
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int a[10000000];
int a1[114514];
bool f(int a,int b){
	return a<b;
}
int main(){
	int n,w,minn; 
	cin>>w>>n;
	for(int i=1;i<=w;i++){
		cin>>a1[i];
	}
	for(int i=1;i<=1000000;i++){
		a[i]=2e9;
	}
	sort(a1,a1+w+1,f);
	for(int i=1;i<=n;i++){
	    for(int j=2;j<=w;j++){
	    	if(i>=a1[j]){
	    		a[i]=min(a[i],a[i-a1[j]]+1);
			}
		}
	}
	cout<<a[n];
}