题目描述

某国有 n 种纸币，每种纸币面额为 ai​ 并且有无限张，现在要凑出 w 的金额，试问最少用多少张纸币可以凑出来？

输入格式

第一行两个整数 n,w，分别表示纸币的种数和要凑出的金额。
第二行一行 n 个以空格隔开的整数 a1​,a2​,a3​,…an​ 依次表示这 n 种纸币的面额。

输出格式

一行一个整数，表示最少使用的纸币张数。

输入输出样例

输入 #1

6 15
1 5 10 20 50 100

输出 #1

2

输入 #2

3 15
1 5 11

输出 #2

3

说明/提示

对于 40% 的数据，满足 n≤10，w≤100；
对于 100% 的数据，满足 1≤n≤103，1≤ai​≤w≤104。

思路：

我们如果需要得目标T最少需要多少张，那么我们可以考虑T-k最少需要多少张（k为已有的纸币的面额），因为这样的话，我们便可直接在此基础上加1得到。所以我们需要将比T小的面额的最小张数求出来，这样便可推出T。

我们规定dp[i]为得到面额为i时，需要的最少纸币数。

实现：

我们从小到大依次求解，由于纸币数量无限，所以内层循环每次会遍历完所有的面额。

由于要求最小数量，所以，我们需要将当前的dp[i]和dp[i-k]（k为目前遍历到的面额）作比较，取最小的即可。

注意：我们需要对dp数组进行初始化。dp[0]不需要任何纸币，所以为0。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

typedef struct Group{
	int x,y;
	bool operator<(Group g) const{
		if(x!=g.x) return x<g.x;
		else return y<g.y;
	}	
}G;


int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	
	int n,w;
	cin>>n>>w;
	vector<int> nums;
	int maxn = INT_MIN;
	for(int i=0; i<n; i++){
		int t;
		cin>>t;
		nums.push_back(t);
	}
	
	vector<int> dp(w+1,INT_MAX);
	dp[0]=0;
	
	for(int i=1; i<=w; i++){
		for(int j=0; j<n; j++){
			if(i>=nums[j]&&dp[i-nums[j]]!=INT_MAX) dp[i] = min(dp[i], dp[i-nums[j]]+1);
		}
//		cout<<dp[i]<<endl;
	}
	
	cout<<dp[w]<<endl;
	return 0;
}