自动搬运

查看原文

来自洛谷，原作者为

	sgl654321 风起雨停，天又放晴

搬运于2025-08-24 21:42:11，当前版本为作者最后更新于2023-03-18 15:48:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目描述

$n$ 种纸币，要想凑出 $w$ 的面值，至少要几张纸币？

解题思路

一眼 dp 题。dp 题的解题思路通常为：读懂题意，设计状态，确定目标态和初始态，思考转移方程，思考优化。

设计状态：$f[i]$ 表示凑出面值为 $i$ 至少需要的纸币张数。

目标态：$f[w]$；初始态：$f[0]=0$，因为凑出 $0$ 元一张纸币都不需要。

转移方程：$f[v]=\min\{f[v-a[i]]\}+1(i\in[1,n])$

这是因为如果 $v-a[i]$ 需要用 $x$ 张纸币，那么只需要加上 $a[i]$ 这一张纸币，就能用这 $x+1$ 张凑出 $v$ 了。

复杂度 $O(nw)$，因此不需要优化。

参考代码

注意：由于涉及到取 $\min$ 操作，所以必须将初始值设为一个极大值。

#include<bits/stdc++.h>
using namespace std;
long long n,w,a[1010],f[100010];
int main(){
	cin>>n>>w;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=10010;i++)f[i]=1145141919;
	for(int i=1;i<=n;i++)
		for(int j=a[i];j<=w;j++)
			f[j]=min(f[j],f[j-a[i]]+1);
	cout<<f[w]<<endl;
	return 0;
}