题目描述
某国有 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;
}
)
