【题目来源】https://www.luogu.com.cn/problem/P2842【题目描述】某国有 n 种纸币每种纸币面额为 ai 并且有无限张现在要凑出 w 的金额试问最少用多少张纸币可以凑出来保证可以凑出对应金额【输入格式】第一行两个整数 nw分别表示纸币的种数和要凑出的金额。第二行一行 n 个以空格隔开的整数 a1a2a3…an 依次表示这 n 种纸币的面额。​​​​​​​【输出格式】一行一个整数表示最少使用的纸币张数。​​​​​​​【输入样例】6 151 5 10 20 50 100​​​​​​​【输出样例】2【数据范围】对于 40% 的数据满足 n≤10w≤100对于 100% 的数据满足 1≤n≤10^31≤ai, w≤10^4。【算法分析】完全背包物品无限选求凑出金额 w 的最少纸币张数。【算法代码一二维数组】状态dp[i][j] 表示考虑前 i 种纸币凑出金额 j所需要的最少纸币张数。转移dp[i][j]min(dp[i-1][j], dp[i][j-ai]1)边界dp[0][0]0其余 dp[0][j]inf。#include bits/stdc.h using namespace std; const int inf0x3f3f3f3f; const int N1e35; const int W1e45; int dp[N][W]; int a[N]; int main() { int n,w; cinnw; for(int i1; in; i) { cina[i]; } memset(dp,inf,sizeof dp); dp[0][0]0; for(int i1; in; i) { for(int j0; jw; j) { dp[i][j]dp[i-1][j]; if(ja[i]) { dp[i][j]min(dp[i][j],dp[i][j-a[i]]1); } } } coutdp[n][w]endl; return 0; } /* in: 6 15 1 5 10 20 50 100 out: 2 */【算法代码二一维数组】状态dp[j] 表示凑出金额 j 需要的最少纸币张数。转移dp[j]min(dp[j], dp[j-a[i]]1)边界- dp[0]0凑 0 元0 张纸币- 其余 dp 初始为无穷大。#include bits/stdc.h using namespace std; const int inf0x3f3f3f3f; const int N1e35; const int W1e45; int dp[W]; int a[N]; int main() { int n,w; cinnw; for(int i1; in; i) { cina[i]; } memset(dp,inf,sizeof dp); dp[0]0; for(int i1; in; i) { for(int ja[i]; jw; j) { dp[j]min(dp[j],dp[j-a[i]]1); } } coutdp[w]endl; return 0; } /* in: 6 15 1 5 10 20 50 100 out: 2 */【参考文献】https://www.bilibili.com/video/BV1xb411e7wwhttps://www.bilibili.com/video/BV1X741127ZM