P2842 纸币问题 1
题目描述
某国有 \(n\) 种纸币，每种纸币面额为 \(a_i\) 并且有无限张，现在要凑出 \(w\) 的金额，试问最少用多少张纸币可以凑出来？（保证可以凑出对应金额）
输入格式
第一行两个整数 \(n,w\)，分别表示纸币的种数和要凑出的金额。
第二行一行 \(n\) 个以空格隔开的整数 \(a_1, a_2, a_3, \dots a_n\) 依次表示这 \(n\) 种纸币的面额。
输出格式
一行一个整数，表示最少使用的纸币张数。
输入输出样例 #1
输入 #1
6 15
1 5 10 20 50 100
输出 #1
2
输入输出样例 #2
输入 #2
3 15
1 5 11
输出 #2
3
说明/提示
对于 \(40\%\) 的数据，满足 \(n\le 10\)，\(w\le 100\)；
对于 \(100\%\) 的数据，满足 \(1\le n\le 10^3\)，\(1\le a_i , w\le 10^4\)。
思路
一开始犹豫了一下，不知道怎么凑面额，后来想到了背包问题，把每个面额想象成一个背包的容量，想到用完全背包，接下来就是想状态转移方程是什么，题目问最小数量纸币，每个纸币转移时就看数量，dp[w] = min(dp[w],dp[w-a[i]]+1)。
正解：
点击查看代码
#include <bits/stdc++.h>
using namespace std;
int n,w,a[1010];
int dp[10100]; //开w容量，不是n
int main()
{cin>>n>>w;for(int i = 1;i <= n;i++) cin>>a[i];memset(dp,0x3f,sizeof(dp)); //赋初值，刚开始不可到达dp[0] = 0;for(int i = 1;i <= n;i++){for(int j = a[i];j <= w;j++){dp[j] = min(dp[j],dp[j-a[i]]+1);}}cout<<dp[w];
}
//唯一需要注意的是赋初值的时候所有容量赋成无穷大，dp[0] = 0。